Faangprep Logo
LoginRegister
Browse Curriculum

Rat in a Maze

Given a N*N maze with some obstacles, starting from the top-left corner, finding a path to reach the bottom-right corner.

Rat in a Maze

Ready

See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine a rat starts at the source and wants to reach the destination. The rat can move in four directions: up, down, left, right. It cannot move to a blocked cell or a cell it has already visited in the current path. If it hits a dead end, it backtracks.

Concept

Key Concepts:

  1. Grid Traversal: Moving through a 2D array.
  2. State Management: Keeping track of visited cells to avoid cycles.
  3. Backtracking: Exploring a path, and if it fails, undoing the last move to try a different direction.
  4. Directions: Typically Down, Right, Up, Left (lexicographical order if required).

How it Works

  1. Start at (0, 0).
  2. Mark the current cell as part of the solution path.
  3. Try moving in allowed directions (e.g., D, L, R, U).
  4. Check if the next cell is safe (within bounds, open, not visited).
  5. If safe, recursively jump to that cell.
  6. If the recursion returns true (destination found), propagate true up.
  7. If all directions fail, unmark the current cell (backtrack) and return false.

Step-by-Step Breakdown

Example 3x3 Maze:

  • Start (0,0). Valid. Path: [(0,0)]
  • Try Down (1,0): Wall.
  • Try Right (0,1): Valid. Path: [(0,0), (0,1)]
  • From (0,1), Try Down (1,1): Valid. Path: ...
  • Continue until (N-1, N-1) is reached.
  • If stuck, remove last cell from path and try next direction.

When to Use

  • Pathfinding in grids with obstacles.
  • Generating all possible paths in a maze.
  • Robotics path planning (basic).

When NOT to Use

  • Finding the shortest path in an unweighted graph (use BFS).
  • Large open grids where A* or other heuristic search is more efficient.

How to Identify

"Find path in a grid", "Maze", "Rat", "Reach destination".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep