Loading…

mediumBacktrackingFrequently asked

Rat in a Maze

Q: How do you solve Rat in a Maze using the Down/Right-Only DFS (Simplest Case) approach?

When to use it: Use as a warm-up if movement is restricted to down and right — no cycles, so no unmarking is needed. Handle the restricted version first: the rat moves only right or down. **No cycles, no marking.** Right and down both strictly increase a coordinate, so the rat can never return to a visited cell. That removes the need for a visited grid and the unmark step — the structure simplifies to plain DFS. **The recursion.** From `(r, c)`, if it's the goal return true. Otherwise try moving right and down; return true if either reaches the goal through open, in-bounds cells. **Why mention it.** It isolates the core 'try each move, recurse' idea before adding the complication of cycles. It also opens the door to DP: since subproblems repeat, memoizing on `(r, c)` collapses the exponential tree to O(R·C). **Limitation.** It only works when backward moves are forbidden. The moment Left/Up are allowed, cycles appear and you need the full visited-and-backtrack machinery. Time complexity: O(2^(R+C)). Space complexity: O(R + C).

Q: How do you solve Rat in a Maze using the Four-Direction Backtracking (Optimal General Case) approach?

When to use it: The full answer. Phrase it as 'mark the cell on the current path, try all four directions, unmark when backing out'. Run depth-first search that records which cells are on the current path and rolls each choice back. **Choose.** At cell `(r, c)`, first reject it if it's off the grid, a wall, or already on the current path. If it's the goal, you've found a path. Otherwise mark `(r, c)` as visited — it's now part of the path you're building. **Explore.** Try the four directions in a fixed order (Down, Left, Right, Up). Each recursive call attempts to extend the path through that neighbor. Using a consistent order makes any listed paths come out in lexicographic order. **Unchoose (the heart of backtracking).** After all four directions return, **unmark** `(r, c)`. This is the step beginners drop. Without it, a cell explored on one dead-end path stays blocked forever, so genuinely valid paths that reuse that cell are never found. Unmarking restores the grid to exactly its state before this call, so sibling branches start clean. **One path vs all paths.** To answer 'does a path exist', propagate a boolean and return true as soon as the goal is hit — the early return prunes the rest. To count or list every path, don't early-return on success: record the path (or increment a counter) and keep exploring other directions; the unmark step is what makes enumerating distinct paths correct. **Why the visited grid is mandatory here.** With Left and Up allowed, two open cells form a cycle. Without the visited check the rat oscillates between them forever. Marking the current path breaks every cycle while still allowing different paths to share cells across separate branches. Time complexity: O(4^(R·C)). Space complexity: O(R·C).

Backtracking · 9 of 13 · 11 min

You are given an R × C grid maze of 0s and 1s, where 1 is an open cell and 0 is a wall. A rat starts at the top-left cell (0, 0) and wants to reach the bottom-right cell (R - 1, C - 1), moving one step at a time to an adjacent open cell.

Allowed moves are Down, Left, Right, and Up (the rat may not revisit a cell on its current path).

Return whether a path exists (and, in the all-paths variant, list every distinct path as a string of move letters). If the start or goal is a wall, no path exists.

In plain English

Walk a depth-first search from the start, trying each legal direction in a fixed order. A path is a sequence of open cells with no repeats. Marking the current cell as on-path prevents loops; unmarking on the way back lets the cell be part of other paths. The same recursion answers 'does a path exist', 'how many paths', or 'list all paths'.

Examples

Example 1

Input: maze = [[1,0,0],[1,1,0],[0,1,1]]
Output: true (path DDRD-style: (0,0)->(1,0)->(1,1)->(2,1)->(2,2))
Note: Down to (1,0), Right to (1,1), Down to (2,1), Right to (2,2). All open, reaches the goal.

Example 2

Input: maze = [[1,0],[0,1]]
Output: false
Note: From (0,0) the only neighbors (0,1) and (1,0) are walls, so the rat is trapped.

Example 3

Input: maze = [[1,1],[1,1]]
Output: true
Note: Fully open 2×2; e.g. Right then Down reaches (1,1).

Constraints

1 ≤ R, C ≤ 10 (small enough for backtracking)
maze[i][j] ∈ {0, 1}
The rat cannot step on a 0 cell or leave the grid
A cell cannot be revisited within the same path

Clarifying questions4First question: Which moves are allowed — only down/right, or all four directions?Explore questions

Q1.Which moves are allowed — only down/right, or all four directions?
I'll assume all four (D, L, R, U). With only down/right there are no cycles, so the visited grid becomes optional and DP is possible.
Q2.Do I return one path, count them, or list them all?
I'll show the one-path existence check and note the one-line change to count or list every path.
Q3.Can the start or goal be a wall?
Possibly — if either is 0, the answer is immediately no path. I guard that up front.
Q4.Should the path letters follow a specific order?
Fixing the direction order (Down, Left, Right, Up) makes listed paths come out in lexicographic order, which interviewers often expect.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

From the top-left cell, try to reach the bottom-right by stepping only onto open cells. Backtrack: at each cell try each allowed direction in order, mark the cell visited, recurse, and unmark it when you back out so other paths can reuse it. To find one path, return as soon as you reach the goal; to count or list all paths, keep going after each success. With 4 directions the worst case is O(4^(R·C))-ish, pruned hard by walls and the visited grid.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write clean grid backtracking with correct mark/unmark, bounds and wall checks, and adapt between 'find one path' and 'count/list all paths'.

Where candidates slip

Marking a cell visited but never unmarking on the way out, which blocks alternative paths, or checking bounds after indexing the grid (out-of-range access).

How to stand out

State the choose-explore-unchoose structure, fix a deterministic direction order, and explain how the same skeleton switches between one-path and all-paths by changing the return behavior.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Down/Right-Only DFS (Simplest Case)	`O(2^(R+C))`	`O(R + C)`	Use as a warm-up if movement is restricted to down and right — no cycles, so no unmarking is needed.	Read
2	Four-Direction Backtracking (Optimal General Case)Optimal	`O(4^(R·C))`	`O(R·C)`	The full answer. Phrase it as 'mark the cell on the current path, try all four directions, unmark when backing out'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewReach bottom-right in a grid?Need shortest path only?YesNo, all moves / enumerateExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Down/Right-Only DFS (Simplest Case)

TimeO(2^(R+C))SpaceO(R + C)

Use as a warm-up if movement is restricted to down and right — no cycles, so no unmarking is needed.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the rat may only move down or right, can it ever revisit a cell? What does that mean for the visited grid?

2Hint 2Explore hint

Recurse: at (r, c) try moving right to (r, c+1) and down to (r+1, c) if those cells are open and in bounds.

3Hint 3Explore hint

Because moves are monotonic, no cycle is possible, so you don't need to mark/unmark — just recurse and OR the results.

A · Core idea

Handle the restricted version first: the rat moves only right or down.

No cycles, no marking. Right and down both strictly increase a coordinate, so the rat can never return to a visited cell. That removes the need for a visited grid and the unmark step — the structure simplifies to plain DFS.

The recursion. From (r, c), if it's the goal return true. Otherwise try moving right and down; return true if either reaches the goal through open, in-bounds cells.

Why mention it. It isolates the core 'try each move, recurse' idea before adding the complication of cycles. It also opens the door to DP: since subproblems repeat, memoizing on (r, c) collapses the exponential tree to O(R·C).

Limitation. It only works when backward moves are forbidden. The moment Left/Up are allowed, cycles appear and you need the full visited-and-backtrack machinery.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

maze = [[1,1],[0,1]]

Interactive diagram

Down/right recursion tree

(0,0)

Active call / nodeSupporting contextReturned stateNot active

Each node branches into right and down; one branch reaches the goal.

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean hasPathDownRight(int[][] maze) { int R = maze.length, C = maze[0].length; if (maze[0][0] == 0 || maze[R - 1][C - 1] == 0) return false; return dfs(maze, 0, 0, R, C); }Explore the full code

solution.javaJava

Down/Right-Only DFS (Simplest Case) — reference

3 teaching notes

1
public boolean hasPathDownRight(int[][] maze) {
2
    int R = maze.length, C = maze[0].length;
3
    // A walled start or goal means no path exists.
4
    if (maze[0][0] == 0 || maze[R - 1][C - 1] == 0) return false;
5
    return dfs(maze, 0, 0, R, C);
6
}
7
 
8
private boolean dfs(int[][] maze, int r, int c, int R, int C) {
9
    // Reject off-grid or blocked cells before going deeper.
10
    if (r >= R || c >= C || maze[r][c] == 0) return false;
11
    if (r == R - 1 && c == C - 1) return true;
12
    // Try right then down; short-circuit OR stops at the first success.
13
    return dfs(maze, r, c + 1, R, C) || dfs(maze, r + 1, c, R, C);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(2^(R+C)) timeO(R + C) spaceOpen the invariant and proofExplore the proof

Restricting moves to down/right removes cycles entirely, which is why this variant needs no backtracking. Recognizing when a problem is acyclic tells you whether you can drop the mark/unmark bookkeeping (and even switch to DP).

ComplexityO(2^(R+C)) time, O(R + C) space — Each call branches into at most 2 moves and the path length is R + C - 1, so the tree has O(2^(R+C)) leaves in the worst case. Recursion depth is O(R + C). (With memoization on (r, c) this drops to O(R·C).)

E · Edge cases and pitfalls3Indexing maze[r][c] before the bounds check — out-of-range crash.Explore edge cases

Pitfalls

Indexing maze[r][c] before the bounds check — out-of-range crash.
Adding it to a four-direction problem — cycles appear and this version loops or misses paths.
Skipping the walled-endpoint guard.

03.2

Approach 2 of 2 · Optimal

Four-Direction Backtracking (Optimal General Case)

TimeO(4^(R·C))SpaceO(R·C)

The full answer. Phrase it as 'mark the cell on the current path, try all four directions, unmark when backing out'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

With all four moves the rat can loop. How do you stop it from stepping back onto a cell already on the current path?

2Hint 2Explore hint

Keep a visited grid. Mark (r, c) before recursing into neighbors; unmark it after all four directions are tried.

3Hint 3Explore hint

If you reach the goal, you've found a path — return true to stop, or record the move string and continue if you must list every path.

A · Core idea

Run depth-first search that records which cells are on the current path and rolls each choice back.

Choose. At cell (r, c), first reject it if it's off the grid, a wall, or already on the current path. If it's the goal, you've found a path. Otherwise mark (r, c) as visited — it's now part of the path you're building.

Explore. Try the four directions in a fixed order (Down, Left, Right, Up). Each recursive call attempts to extend the path through that neighbor. Using a consistent order makes any listed paths come out in lexicographic order.

Unchoose (the heart of backtracking). After all four directions return, unmark (r, c). This is the step beginners drop. Without it, a cell explored on one dead-end path stays blocked forever, so genuinely valid paths that reuse that cell are never found. Unmarking restores the grid to exactly its state before this call, so sibling branches start clean.

One path vs all paths. To answer 'does a path exist', propagate a boolean and return true as soon as the goal is hit — the early return prunes the rest. To count or list every path, don't early-return on success: record the path (or increment a counter) and keep exploring other directions; the unmark step is what makes enumerating distinct paths correct.

Why the visited grid is mandatory here. With Left and Up allowed, two open cells form a cycle. Without the visited check the rat oscillates between them forever. Marking the current path breaks every cycle while still allowing different paths to share cells across separate branches.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

maze = [[1,0,0],[1,1,0],[0,1,1]], goal (2,2)

Interactive diagram

Backtracking: dead end then unmark

(0,0)

Active call / nodeSupporting contextReturned stateNot active

A dead-end branch unmarks its cells, freeing them for the branch that reaches the goal.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Four-Direction Backtracking (Optimal General Case) — optimal

5 teaching notes

1
// Fixed direction order makes path enumeration deterministic and lexicographic.
2
private static final int[] DR = {1, 0, 0, -1}; // D, L, R, U
3
private static final int[] DC = {0, -1, 1, 0};
4
 
5
public boolean hasPath(int[][] maze) {
6
    int R = maze.length, C = maze[0].length;
7
    if (maze[0][0] == 0 || maze[R - 1][C - 1] == 0) return false;
8
    boolean[][] visited = new boolean[R][C];
9
    return solve(maze, 0, 0, R, C, visited);
10
}
11
 
12
private boolean solve(int[][] maze, int r, int c, int R, int C, boolean[][] visited) {
13
    // Bounds check FIRST, before touching maze[r][c].
14
    if (r < 0 || r >= R || c < 0 || c >= C) return false; // off grid
15
    if (maze[r][c] == 0 || visited[r][c]) return false;    // wall or on path
16
    if (r == R - 1 && c == C - 1) return true;             // goal
17
    // Add this cell to the current path before recursing.
18
    visited[r][c] = true;                                  // choose
19
    for (int d = 0; d < 4; d++) {
20
        if (solve(maze, r + DR[d], c + DC[d], R, C, visited)) {
21
            return true;                                   // one path found
22
        }
23
    }
24
    // Remove it after exploring all directions so other paths can use it.
25
    visited[r][c] = false;                                 // un-choose (backtrack)
26
    return false;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(4^(R·C)) timeO(R·C) spaceOpen the invariant and proofExplore the proof

Backtracking is 'choose, explore, un-choose'. The un-choose is not optional cleanup — it's what separates 'cells on the current path' from 'cells permanently used'. Mark before the recursive calls, unmark after, and a single grid serves every candidate path without interference.

ComplexityO(4^(R·C)) time, O(R·C) space — Each cell branches into up to 4 directions, and a path can touch up to R·C cells, giving a worst-case O(4^(R·C)) search tree. Walls and the visited grid prune this drastically in practice. The visited grid and recursion stack are O(R·C) space.

E · Edge cases and pitfalls7start (0,0) is a wall — Front guard returns false immediately.Explore edge cases

Edge cases handled

start (0,0) is a wallFront guard returns false immediately.
1×1 open grid [[1]]Start equals goal → true with an empty move sequence.
fully blocked except startAll four neighbors are walls; after trying them, unmark and return false.
isolated goal surrounded by wallsSearch exhausts all paths, none reach the goal → false.

Pitfalls

Marking visited but never unmarking — permanently walls off cells and misses valid paths.
Checking maze[r][c] before the bounds check — index out of range.
Early-returning on the first goal when the task is to COUNT or LIST all paths.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewprivate static final int[] DR = {1, 0, 0, -1}; // D, L, R, U private static final int[] DC = {0, -1, 1, 0}; public boolean hasPath(int[][] maze) { int R = maze.length, C = maze[0].length;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

private static final int[] DR = {1, 0, 0, -1}; // D, L, R, U
private static final int[] DC = {0, -1, 1, 0};

public boolean hasPath(int[][] maze) {
    int R = maze.length, C = maze[0].length;
    if (maze[0][0] == 0 || maze[R - 1][C - 1] == 0) return false;
    boolean[][] visited = new boolean[R][C];
    return solve(maze, 0, 0, R, C, visited);
}

private boolean solve(int[][] maze, int r, int c, int R, int C, boolean[][] visited) {
    if (r < 0 || r >= R || c < 0 || c >= C) return false; // off grid
    if (maze[r][c] == 0 || visited[r][c]) return false;    // wall or on path
    if (r == R - 1 && c == C - 1) return true;             // goal
    visited[r][c] = true;                                  // choose
    for (int d = 0; d < 4; d++) {
        if (solve(maze, r + DR[d], c + DC[d], R, C, visited)) {
            return true;                                   // one path found
        }
    }
    visited[r][c] = false;                                 // un-choose (backtrack)
    return false;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the backtrack (no unmark)

If you mark a cell but never clear it, a dead-end exploration leaves the cell flagged as on-path forever, so a different route that needs that cell can never proceed.

Explore the code comparison

Don't write this

visited[r][c] = True
for dr, dc in zip(DR, DC):
    if solve(r + dr, c + dc):
        return True
return False   # WRONG: visited[r][c] never reset

Write this instead

visited[r][c] = True
for dr, dc in zip(DR, DC):
    if solve(r + dr, c + dc):
        return True
visited[r][c] = False   # restore before returning
return False

Bounds check after indexing

Reading maze[r][c] before confirming r and c are in range throws an out-of-bounds error the moment the rat steps off the edge.

Explore the code comparison

Don't write this

if (maze[r][c] == 0) return false;        // crashes if r,c off grid
if (r < 0 || r >= R || c < 0 || c >= C) return false;

Write this instead

if (r < 0 || r >= R || c < 0 || c >= C) return false;
if (maze[r][c] == 0) return false;        // safe now

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Grid backtracking: choose a direction, recurse, undo the choice

Code pattern to memorize

solve(r, c):
    if out of bounds or blocked or visited: return
    if (r, c) == goal: record path; return
    mark visited
    for each allowed (dr, dc):
        solve(r + dr, c + dc)
    unmark visited   # backtrack

Rules to remember

1Mark a cell before recursing and unmark after — forgetting the unmark turns one bad path into a permanent wall.
2Bounds-check and wall-check before stepping; treat off-grid as blocked.
3Fix a direction order (e.g. D, L, R, U) so 'lexicographically smallest path' is well defined.
4To find one path, propagate a boolean success and stop early; to count all, return after exploring every direction without early exit.
5The visited grid prevents cycles — without it the rat can loop forever between two open cells.

Use this pattern when

Find or count paths in a grid with blocked cells and limited moves
Enumerate all routes, not just the shortest one
Constraints make the grid small (backtracking is exponential)
Path must obey movement rules (only down/right, or all four directions)

Choose another pattern when

Only need the SHORTEST path length → BFS in O(R·C), not backtracking
Grid is large and you need any path fast → BFS/DFS with a visited set, no enumeration
Counting paths with only down/right moves and no obstacles → closed-form combinatorics or DP
Weighted cells / minimum cost → Dijkstra or DP, not raw backtracking

Interview takeaway

Rat in a Maze is the template for grid backtracking: mark, explore each direction, unmark. The mark/unmark pairing is the whole trick — it lets a cell belong to many candidate paths without polluting the others.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternRat in a Maze is the canonical grid-backtracking template: choose a cell, explore each direction, un-choose. The mark/unmark pairing recurs in Word Search, Unique Paths III, and N-Queens-style constraint search.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Search
Same grid backtracking with mark/unmark, matching letters instead of reaching a goal cell.
Unique Paths
Coming soon
Down/right only and no obstacles → count paths with DP or a binomial coefficient.
Unique Paths III
Coming soon
Backtracking that must visit every open cell exactly once before reaching the end.
Shortest Path in Binary Matrix
Coming soon
When only the shortest path matters, switch from backtracking to BFS for O(R·C).

Same pattern

←

Knight's Tour (Count / Locate)

Continue · Next problem

Tower of Hanoi

mediumBacktrackingFrequently asked

Rat in a Maze

Backtracking · 9 of 13 · 11 min

Allowed moves are Down, Left, Right, and Up (the rat may not revisit a cell on its current path).

Return whether a path exists (and, in the all-paths variant, list every distinct path as a string of move letters). If the start or goal is a wall, no path exists.

In plain English

Examples

Example 1

Input: maze = [[1,0,0],[1,1,0],[0,1,1]]
Output: true (path DDRD-style: (0,0)->(1,0)->(1,1)->(2,1)->(2,2))
Note: Down to (1,0), Right to (1,1), Down to (2,1), Right to (2,2). All open, reaches the goal.

Example 2

Input: maze = [[1,0],[0,1]]
Output: false
Note: From (0,0) the only neighbors (0,1) and (1,0) are walls, so the rat is trapped.

Example 3

Input: maze = [[1,1],[1,1]]
Output: true
Note: Fully open 2×2; e.g. Right then Down reaches (1,1).

Constraints

1 ≤ R, C ≤ 10 (small enough for backtracking)
maze[i][j] ∈ {0, 1}
The rat cannot step on a 0 cell or leave the grid
A cell cannot be revisited within the same path

Clarifying questions4First question: Which moves are allowed — only down/right, or all four directions?Explore questions

Q1.Which moves are allowed — only down/right, or all four directions?
I'll assume all four (D, L, R, U). With only down/right there are no cycles, so the visited grid becomes optional and DP is possible.
Q2.Do I return one path, count them, or list them all?
I'll show the one-path existence check and note the one-line change to count or list every path.
Q3.Can the start or goal be a wall?
Possibly — if either is 0, the answer is immediately no path. I guard that up front.
Q4.Should the path letters follow a specific order?
Fixing the direction order (Down, Left, Right, Up) makes listed paths come out in lexicographic order, which interviewers often expect.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write clean grid backtracking with correct mark/unmark, bounds and wall checks, and adapt between 'find one path' and 'count/list all paths'.

Where candidates slip

Marking a cell visited but never unmarking on the way out, which blocks alternative paths, or checking bounds after indexing the grid (out-of-range access).

How to stand out

State the choose-explore-unchoose structure, fix a deterministic direction order, and explain how the same skeleton switches between one-path and all-paths by changing the return behavior.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Down/Right-Only DFS (Simplest Case)	`O(2^(R+C))`	`O(R + C)`	Use as a warm-up if movement is restricted to down and right — no cycles, so no unmarking is needed.	Read
2	Four-Direction Backtracking (Optimal General Case)Optimal	`O(4^(R·C))`	`O(R·C)`	The full answer. Phrase it as 'mark the cell on the current path, try all four directions, unmark when backing out'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Down/Right-Only DFS (Simplest Case)

TimeO(2^(R+C))SpaceO(R + C)

Use as a warm-up if movement is restricted to down and right — no cycles, so no unmarking is needed.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the rat may only move down or right, can it ever revisit a cell? What does that mean for the visited grid?

2Hint 2Explore hint

Recurse: at (r, c) try moving right to (r, c+1) and down to (r+1, c) if those cells are open and in bounds.

3Hint 3Explore hint

Because moves are monotonic, no cycle is possible, so you don't need to mark/unmark — just recurse and OR the results.

A · Core idea

Handle the restricted version first: the rat moves only right or down.

The recursion. From (r, c), if it's the goal return true. Otherwise try moving right and down; return true if either reaches the goal through open, in-bounds cells.

Limitation. It only works when backward moves are forbidden. The moment Left/Up are allowed, cycles appear and you need the full visited-and-backtrack machinery.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

maze = [[1,1],[0,1]]

Interactive diagram

Down/right recursion tree

(0,0)

Active call / nodeSupporting contextReturned stateNot active

Each node branches into right and down; one branch reaches the goal.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Down/Right-Only DFS (Simplest Case) — reference

3 teaching notes

1
public boolean hasPathDownRight(int[][] maze) {
2
    int R = maze.length, C = maze[0].length;
3
    // A walled start or goal means no path exists.
4
    if (maze[0][0] == 0 || maze[R - 1][C - 1] == 0) return false;
5
    return dfs(maze, 0, 0, R, C);
6
}
7
 
8
private boolean dfs(int[][] maze, int r, int c, int R, int C) {
9
    // Reject off-grid or blocked cells before going deeper.
10
    if (r >= R || c >= C || maze[r][c] == 0) return false;
11
    if (r == R - 1 && c == C - 1) return true;
12
    // Try right then down; short-circuit OR stops at the first success.
13
    return dfs(maze, r, c + 1, R, C) || dfs(maze, r + 1, c, R, C);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(2^(R+C)) timeO(R + C) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Indexing maze[r][c] before the bounds check — out-of-range crash.Explore edge cases

Pitfalls

Indexing maze[r][c] before the bounds check — out-of-range crash.
Adding it to a four-direction problem — cycles appear and this version loops or misses paths.
Skipping the walled-endpoint guard.

03.2

Approach 2 of 2 · Optimal

Four-Direction Backtracking (Optimal General Case)

TimeO(4^(R·C))SpaceO(R·C)

The full answer. Phrase it as 'mark the cell on the current path, try all four directions, unmark when backing out'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

With all four moves the rat can loop. How do you stop it from stepping back onto a cell already on the current path?

2Hint 2Explore hint

Keep a visited grid. Mark (r, c) before recursing into neighbors; unmark it after all four directions are tried.

3Hint 3Explore hint

If you reach the goal, you've found a path — return true to stop, or record the move string and continue if you must list every path.

A · Core idea

Run depth-first search that records which cells are on the current path and rolls each choice back.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

maze = [[1,0,0],[1,1,0],[0,1,1]], goal (2,2)

Interactive diagram

Backtracking: dead end then unmark

(0,0)

Active call / nodeSupporting contextReturned stateNot active

A dead-end branch unmarks its cells, freeing them for the branch that reaches the goal.

Final resulttrue

C · Code with teaching comments

solution.javaJava

Four-Direction Backtracking (Optimal General Case) — optimal

5 teaching notes

1
// Fixed direction order makes path enumeration deterministic and lexicographic.
2
private static final int[] DR = {1, 0, 0, -1}; // D, L, R, U
3
private static final int[] DC = {0, -1, 1, 0};
4
 
5
public boolean hasPath(int[][] maze) {
6
    int R = maze.length, C = maze[0].length;
7
    if (maze[0][0] == 0 || maze[R - 1][C - 1] == 0) return false;
8
    boolean[][] visited = new boolean[R][C];
9
    return solve(maze, 0, 0, R, C, visited);
10
}
11
 
12
private boolean solve(int[][] maze, int r, int c, int R, int C, boolean[][] visited) {
13
    // Bounds check FIRST, before touching maze[r][c].
14
    if (r < 0 || r >= R || c < 0 || c >= C) return false; // off grid
15
    if (maze[r][c] == 0 || visited[r][c]) return false;    // wall or on path
16
    if (r == R - 1 && c == C - 1) return true;             // goal
17
    // Add this cell to the current path before recursing.
18
    visited[r][c] = true;                                  // choose
19
    for (int d = 0; d < 4; d++) {
20
        if (solve(maze, r + DR[d], c + DC[d], R, C, visited)) {
21
            return true;                                   // one path found
22
        }
23
    }
24
    // Remove it after exploring all directions so other paths can use it.
25
    visited[r][c] = false;                                 // un-choose (backtrack)
26
    return false;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(4^(R·C)) timeO(R·C) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7start (0,0) is a wall — Front guard returns false immediately.Explore edge cases

Edge cases handled

start (0,0) is a wallFront guard returns false immediately.
1×1 open grid [[1]]Start equals goal → true with an empty move sequence.
fully blocked except startAll four neighbors are walls; after trying them, unmark and return false.
isolated goal surrounded by wallsSearch exhausts all paths, none reach the goal → false.

Pitfalls

Marking visited but never unmarking — permanently walls off cells and misses valid paths.
Checking maze[r][c] before the bounds check — index out of range.
Early-returning on the first goal when the task is to COUNT or LIST all paths.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

private static final int[] DR = {1, 0, 0, -1}; // D, L, R, U
private static final int[] DC = {0, -1, 1, 0};

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the backtrack (no unmark)

If you mark a cell but never clear it, a dead-end exploration leaves the cell flagged as on-path forever, so a different route that needs that cell can never proceed.

Explore the code comparison

Don't write this

visited[r][c] = True
for dr, dc in zip(DR, DC):
    if solve(r + dr, c + dc):
        return True
return False   # WRONG: visited[r][c] never reset

Write this instead

visited[r][c] = True
for dr, dc in zip(DR, DC):
    if solve(r + dr, c + dc):
        return True
visited[r][c] = False   # restore before returning
return False

Bounds check after indexing

Reading maze[r][c] before confirming r and c are in range throws an out-of-bounds error the moment the rat steps off the edge.

Explore the code comparison

Don't write this

if (maze[r][c] == 0) return false;        // crashes if r,c off grid
if (r < 0 || r >= R || c < 0 || c >= C) return false;

Write this instead

if (r < 0 || r >= R || c < 0 || c >= C) return false;
if (maze[r][c] == 0) return false;        // safe now

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Grid backtracking: choose a direction, recurse, undo the choice

Code pattern to memorize

solve(r, c):
    if out of bounds or blocked or visited: return
    if (r, c) == goal: record path; return
    mark visited
    for each allowed (dr, dc):
        solve(r + dr, c + dc)
    unmark visited   # backtrack

Rules to remember

1Mark a cell before recursing and unmark after — forgetting the unmark turns one bad path into a permanent wall.
2Bounds-check and wall-check before stepping; treat off-grid as blocked.
3Fix a direction order (e.g. D, L, R, U) so 'lexicographically smallest path' is well defined.
4To find one path, propagate a boolean success and stop early; to count all, return after exploring every direction without early exit.
5The visited grid prevents cycles — without it the rat can loop forever between two open cells.

Use this pattern when

Find or count paths in a grid with blocked cells and limited moves
Enumerate all routes, not just the shortest one
Constraints make the grid small (backtracking is exponential)
Path must obey movement rules (only down/right, or all four directions)

Choose another pattern when

Only need the SHORTEST path length → BFS in O(R·C), not backtracking
Grid is large and you need any path fast → BFS/DFS with a visited set, no enumeration
Counting paths with only down/right moves and no obstacles → closed-form combinatorics or DP
Weighted cells / minimum cost → Dijkstra or DP, not raw backtracking

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Search
Same grid backtracking with mark/unmark, matching letters instead of reaching a goal cell.
Unique Paths
Coming soon
Down/right only and no obstacles → count paths with DP or a binomial coefficient.
Unique Paths III
Coming soon
Backtracking that must visit every open cell exactly once before reaching the end.
Shortest Path in Binary Matrix
Coming soon
When only the shortest path matters, switch from backtracking to BFS for O(R·C).

Same pattern

←

Knight's Tour (Count / Locate)

Continue · Next problem

Tower of Hanoi