Loading…

mediumDynamic ProgrammingLC #63Frequently asked

Count Paths in a Grid with Obstacles

Q: How do you solve Count Paths in a Grid with Obstacles using the Brute Force — Recursion Over Right/Down Choices approach?

When to use it: Say this first to establish the 'paths = from above + from left' recurrence and the obstacle/boundary rules, then flag the exponential branching. Define `solve(i, j)` = the number of distinct right/down paths from the start `(0, 0)` to cell `(i, j)`. - If `(i, j)` is blocked, no path can be on it → 0. - If `(i, j)` is the start and it's free → 1 (the empty path). - Otherwise sum the paths arriving from the only two cells you could have stepped from: above `solve(i-1, j)` (if `i > 0`) and left `solve(i, j-1)` (if `j > 0`). **Why the recurrence sums exactly two predecessors.** The robot moves only right or down, so the last step onto `(i, j)` was either a downward step from `(i-1, j)` or a rightward step from `(i, j-1)`. Every path to `(i, j)` ends with one of those two steps, and the two sets are disjoint (they differ in the final move), so the count is the sum of the counts to those predecessors. This 'sum the ways into my predecessors' is the defining shape of a counting DP on a DAG. **Why blocked cells are a hard zero.** A blocked cell can never be stood on, so zero paths reach it and it forwards zero to its successors. Returning 0 there automatically routes the count around obstacles — no special-casing of neighbours needed. **Why boundaries contribute 0, not 1.** A cell in the top row has no cell above it; a cell in the left column has none to its left. Treating those missing predecessors as 0 (rather than skipping the base case) keeps the recurrence uniform. Only the start seeds a 1. **Why we don't ship this.** `solve(i-1, j)` and `solve(i, j-1)` both recurse into `solve(i-1, j-1)`, and so on, so the same cell is recomputed exponentially often. Caching `solve(i, j)` collapses it to `O(m·n)`. Time complexity: O(2^(m+n)). Space complexity: O(m + n).

Q: How do you solve Count Paths in a Grid with Obstacles using the Top-Down Memoization on (i, j) approach?

When to use it: The fix once you name the overlap — 'cache solve(i, j) so each cell is computed once'. Keep the 'sum of two predecessors' recurrence but cache `solve(i, j)` so each cell is computed once. **The mental shift: the count into a cell is fixed.** However the recursion reaches `(i, j)`, the number of paths from the start to that cell is a single value. Caching by `(i, j)` removes all the duplicated subtrees, leaving `O(m·n)` distinct cells each resolved in `O(1)`. **Sentinel choice.** Initialise the memo to -1 for 'uncomputed' — real path counts are non-negative, and a free start legitimately returns 1, so 0 can't double as 'empty'. Blocked cells return 0 before any caching. **A language note (Java memo vs Python tabulation).** This recursion nests up to `O(m + n)` deep. For the 100×100 bound that's ~200 — fine in both languages. But for very large grids the depth could approach **Python's default recursion limit of about 1000**, at which point you'd raise the limit with `sys.setrecursionlimit` or, cleaner, switch to the bottom-up table (next approach) that uses no stack at all. Top-down memoization is the natural default in Java; bottom-up is the safer default in Python once grids get tall or wide. Time complexity: O(m·n). Space complexity: O(m·n).

LCPractice

Dynamic Programming · 28 of 44 · 11 min

You are given an m × n integer grid where grid[i][j] = 0 means the cell is free and grid[i][j] = 1 means it is blocked by an obstacle.

A robot starts at the top-left cell (0, 0) and wants to reach the bottom-right cell (m-1, n-1). It can move only right or down at each step, and it cannot enter a blocked cell.

Return the **number of distinct paths** the robot can take. If the start or destination is blocked, the answer is 0.

In plain English

Think of each free cell as a node that can be reached from the cell directly above it or directly to its left, since those are the only moves that land on it. The number of ways to reach a cell is therefore the sum of the ways to reach those two predecessors. Blocked cells are dead — zero ways in, zero ways out. Counting bottom-up from the start fills the grid so the bottom-right cell holds the total number of obstacle-free right/down paths.

Examples

Example 1

Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Note: The obstacle at the center forces the two routes: right→right→down→down and down→down→right→right.

Example 2

Input: grid = [[0,1],[0,0]]
Output: 1
Note: The only path is down then right; the obstacle at (0,1) blocks the right-first route.

Example 3

Input: grid = [[1,0],[0,0]]
Output: 0
Note: The start is blocked, so no path can even begin — zero ways.

Constraints

1 ≤ m, n ≤ 100
grid[i][j] is 0 (free) or 1 (blocked)
Moves are restricted to right and down
The path count can be large but fits in a 64-bit integer for these bounds

Clarifying questions4First question: Which moves are allowed?Explore questions

Q1.Which moves are allowed?
Only right and down. That monotonicity is what makes it a clean DAG DP — a cell's only predecessors are above and to the left, so there are no cycles.
Q2.What if the start or end cell is blocked?
Then there are zero paths. A blocked start makes dp[0][0] = 0, which propagates; a blocked end makes dp[m-1][n-1] = 0 directly.
Q3.Can a path revisit a cell?
No — with only right/down moves you always make progress toward the corner, so cells are never revisited. That's why it's a counting DP, not a search.
Q4.Could the count overflow?
For 100×100 the count can be astronomically large in theory, but the obstacle version stays within 64-bit for the given bounds. If asked, I'd switch to a big integer or a modulus.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count the ways to walk from the top-left to the bottom-right of an m×n grid, moving only right or down, where some cells are blocked. It's a grid DP: dp[i][j] = number of paths reaching cell (i, j). A blocked cell has 0 paths; otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1] (paths arriving from above plus from the left). Seed dp[0][0] = 1 only if the start is free. O(m·n) time, reducible to O(n) space. The trap is an obstacle on the start or in the first row/column — it zeroes out everything downstream of it.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you set up dp[i][j] = dp[i-1][j] + dp[i][j-1], force blocked cells to 0, seed the start correctly, and handle obstacles in the first row/column that zero out the rest of that line.

Where candidates slip

Hard-coding dp[0][0] = 1 without checking the start is free, initializing the whole first row/column to 1 ignoring obstacles, or counting a blocked cell as passable.

How to stand out

State the move constraint that gives the recurrence (right/down → from above or left), explain why a blocked first-row cell zeroes everything after it, then offer the O(n) rolling-row compression and note the no-obstacle closed form.

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	Brute Force — Recursion Over Right/Down Choices	`O(2^(m+n))`	`O(m + n)`	Say this first to establish the 'paths = from above + from left' recurrence and the obstacle/boundary rules, then flag the exponential branching.	Read
2	Top-Down Memoization on (i, j)	`O(m·n)`	`O(m·n)`	The fix once you name the overlap — 'cache solve(i, j) so each cell is computed once'.	Read
3	Bottom-Up — Grid Table, Rolling Row (Optimal)Optimal	`O(m·n)`	`O(n) with a rolling row`	The answer they want. Frame it as 'dp[i][j] = up + left, sweep row by row', then compress to one row.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCount top-left to bottom-right pathsAny obstacles?NoYesExplore 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 3

Brute Force — Recursion Over Right/Down Choices

TimeO(2^(m+n))SpaceO(m + n)

Say this first to establish the 'paths = from above + from left' recurrence and the obstacle/boundary rules, then flag the exponential branching.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At each free cell you can go right or down. How many ways reach a given cell? Sum the ways that reach the cells you could have stepped from.

2Hint 2Explore hint

Define solve(i, j) = number of paths from the start to cell (i, j). It comes from the cell above and the cell to the left.

3Hint 3Explore hint

Base cases: a blocked cell has 0 paths; the start (0,0) has 1 if free. Out-of-bounds predecessors contribute 0.

A · Core idea

Define solve(i, j) = the number of distinct right/down paths from the start (0, 0) to cell (i, j).

If (i, j) is blocked, no path can be on it → 0.
If (i, j) is the start and it's free → 1 (the empty path).
Otherwise sum the paths arriving from the only two cells you could have stepped from: above solve(i-1, j) (if i > 0) and left solve(i, j-1) (if j > 0).

Why the recurrence sums exactly two predecessors. The robot moves only right or down, so the last step onto (i, j) was either a downward step from (i-1, j) or a rightward step from (i, j-1). Every path to (i, j) ends with one of those two steps, and the two sets are disjoint (they differ in the final move), so the count is the sum of the counts to those predecessors. This 'sum the ways into my predecessors' is the defining shape of a counting DP on a DAG.

Why blocked cells are a hard zero. A blocked cell can never be stood on, so zero paths reach it and it forwards zero to its successors. Returning 0 there automatically routes the count around obstacles — no special-casing of neighbours needed.

Why boundaries contribute 0, not 1. A cell in the top row has no cell above it; a cell in the left column has none to its left. Treating those missing predecessors as 0 (rather than skipping the base case) keeps the recurrence uniform. Only the start seeds a 1.

Why we don't ship this. solve(i-1, j) and solve(i, j-1) both recurse into solve(i-1, j-1), and so on, so the same cell is recomputed exponentially often. Caching solve(i, j) collapses it to O(m·n).

B · Visual dry run

Interactive dry run

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

grid = [[0,0],[0,0]] (no obstacles, 2×2)

Live grid state

Cells change as the traversal moves

solve(0,0)

00,0

00,1

01,0

01,1

Current traversalVisited / sunkUnvisited land

free start

Final result2

C · Code with teaching comments

Reference implementation previewpublic int uniquePathsWithObstacles(int[][] grid) { int m = grid.length, n = grid[0].length; return solve(grid, m - 1, n - 1); } Explore the full code

solution.javaJava

Brute Force — Recursion Over Right/Down Choices — reference

3 teaching notes

1
public int uniquePathsWithObstacles(int[][] grid) {
2
    int m = grid.length, n = grid[0].length;
3
    return solve(grid, m - 1, n - 1);
4
}
5
 
6
// paths from (0,0) to (i,j)
7
private int solve(int[][] grid, int i, int j) {
8
    // Out-of-bounds or blocked → 0 paths. Folds the boundary and obstacle cases into
9
    // one guard.
10
    if (i < 0 || j < 0 || grid[i][j] == 1) {
11
        return 0;
12
    }
13
    // The free start is the single seed of 1 path.
14
    if (i == 0 && j == 0) {
15
        return 1;
16
    }
17
    // Paths arriving from above plus paths arriving from the left.
18
    return solve(grid, i - 1, j) + solve(grid, i, j - 1);
19
}

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

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

The state is the cell (i, j) and the recursion revisits the same cell through many path prefixes. A 2-D grid state plus exponential overlap is the textbook signal for an O(m·n) DP.

ComplexityO(2^(m+n)) time, O(m + n) space — Each cell branches into its two predecessors and those branches overlap heavily; the unmemoized tree is exponential in m + n. Recursion depth is O(m + n).

E · Edge cases and pitfalls5blocked start — grid[0][0] == 1 → solve returns 0 immediately.Explore edge cases

Edge cases handled

blocked startgrid[0][0] == 1 → solve returns 0 immediately.
1×1 free gridStart equals end and is free → 1 path.

Pitfalls

Returning 1 for out-of-bounds predecessors instead of 0 — over-counts along the borders.
Forgetting the obstacle check before the start check — a blocked start would wrongly return 1.
Skipping this approach — the 'sum of two predecessors' recurrence is what the interviewer wants verbalized.

03.2

Approach 2 of 3

Top-Down Memoization on (i, j)

TimeO(m·n)SpaceO(m·n)

The fix once you name the overlap — 'cache solve(i, j) so each cell is computed once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

solve(i, j) returns the same count every call. Where can you store it so each cell is computed once?

2Hint 2Explore hint

Use a 2-D memo of size m × n. Mark cells 'uncomputed' with -1 (real counts are ≥ 0), check on entry, store before returning.

3Hint 3Explore hint

There are O(m·n) cells and each does O(1) work → O(m·n) time and space.

A · Core idea

Keep the 'sum of two predecessors' recurrence but cache solve(i, j) so each cell is computed once.

The mental shift: the count into a cell is fixed. However the recursion reaches (i, j), the number of paths from the start to that cell is a single value. Caching by (i, j) removes all the duplicated subtrees, leaving O(m·n) distinct cells each resolved in O(1).

Sentinel choice. Initialise the memo to -1 for 'uncomputed' — real path counts are non-negative, and a free start legitimately returns 1, so 0 can't double as 'empty'. Blocked cells return 0 before any caching.

A language note (Java memo vs Python tabulation). This recursion nests up to O(m + n) deep. For the 100×100 bound that's ~200 — fine in both languages. But for very large grids the depth could approach Python's default recursion limit of about 1000, at which point you'd raise the limit with sys.setrecursionlimit or, cleaner, switch to the bottom-up table (next approach) that uses no stack at all. Top-down memoization is the natural default in Java; bottom-up is the safer default in Python once grids get tall or wide.

B · Visual dry run

Interactive dry run

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

grid = [[0,0,0],[0,1,0],[0,0,0]]

Live grid state

Cells change as the traversal moves

top row & left col

00,0

00,1

00,2

01,0

11,1

01,2

02,0

02,1

02,2

Current traversalVisited / sunkUnvisited land

all reachable cells cache 1 (single direction in)

Final result2

C · Code with teaching comments

Reference implementation previewpublic int uniquePathsWithObstacles(int[][] grid) { int m = grid.length, n = grid[0].length; Integer[][] memo = new Integer[m][n]; return solve(grid, m - 1, n - 1, memo); }Explore the full code

solution.javaJava

Top-Down Memoization on (i, j) — reference

3 teaching notes

1
public int uniquePathsWithObstacles(int[][] grid) {
2
    int m = grid.length, n = grid[0].length;
3
    // null marks 'uncomputed' — a free start returns 1, so 0 can't mean empty.
4
    Integer[][] memo = new Integer[m][n];
5
    return solve(grid, m - 1, n - 1, memo);
6
}
7
 
8
private int solve(int[][] grid, int i, int j, Integer[][] memo) {
9
    if (i < 0 || j < 0 || grid[i][j] == 1) {
10
        return 0;
11
    }
12
    if (i == 0 && j == 0) {
13
        return 1;
14
    }
15
    // Cache hit returns the stored count in O(1).
16
    if (memo[i][j] != null) {
17
        return memo[i][j];
18
    }
19
    // Store the summed predecessors before returning so the cell is never recomputed.
20
    memo[i][j] = solve(grid, i - 1, j, memo) + solve(grid, i, j - 1, memo);
21
    return memo[i][j];
22
}

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

D · Why it works and complexityO(m·n) timeO(m·n) spaceOpen the invariant and proofExplore the proof

Standard DP upgrade: the correct recurrence plus a cache keyed on the cell (i, j). The thinking — two predecessors, obstacle = 0, free start = 1 — was done in the brute force.

ComplexityO(m·n) time, O(m·n) space — There are m·n distinct (i, j) states; each combines two cached sub-results in O(1) → O(m·n) time. The memo is O(m·n); recursion depth is O(m + n) on top.

E · Edge cases and pitfalls5obstacle blocking all routes — Every path to the end passes a blocked cell → end cell caches 0.Explore edge cases

Edge cases handled

obstacle blocking all routesEvery path to the end passes a blocked cell → end cell caches 0.
large grid in PythonDepth m+n may near the recursion limit; raise it or use the table.

Pitfalls

Using 0 as the sentinel — a free start returns 1 and blocked cells return 0, so 0 is a real value; use null/-1.
Checking the start base case before the obstacle guard — a blocked start would wrongly return 1.
Deep recursion in Python on tall/wide grids — tabulation avoids the stack.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Grid Table, Rolling Row (Optimal)

TimeO(m·n)SpaceO(n) with a rolling row

The answer they want. Frame it as 'dp[i][j] = up + left, sweep row by row', then compress to one row.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp[i][j] = number of paths to cell (i, j). Fill row by row, left to right, so the cell above and the cell to the left are already done.

2Hint 2Explore hint

Seed dp[0][0] = 1 if the start is free, else 0. A blocked cell sets dp[i][j] = 0; otherwise dp[i][j] = up + left (treat off-grid as 0).

3Hint 3Explore hint

Since row i depends only on row i-1 and the cell to its left, keep a single rolling row of length n → O(n) space. Answer is the last cell.

A · Core idea

Let dp[i][j] be the number of right/down paths from the start to cell (i, j). Sweep the grid top to bottom, left to right, so both predecessors are already computed when you reach a cell. The answer is dp[m-1][n-1].

Seeding the start. dp[0][0] = 1 only if (0, 0) is free; if the start is blocked it's 0 and the whole grid stays 0. This single check is the most-missed detail — hard-coding dp[0][0] = 1 reports phantom paths through a blocked start.

The fill rule. For every other cell: if it's blocked, dp[i][j] = 0; otherwise dp[i][j] = up + left, where up = dp[i-1][j] (0 if i == 0) and left = dp[i][j-1] (0 if j == 0). Treating off-grid predecessors as 0 makes the first row and first column fall out naturally — each has just one incoming direction.

Why obstacles in the first row/column are sharp. In the top row a cell's only predecessor is its left neighbour; once an obstacle sets a cell to 0, every cell to its right inherits left = 0 and stays 0. The first column behaves the same vertically. Initializing borders to a blanket 1 (a common bug) ignores this and over-counts.

Why the sweep order is valid. dp[i][j] reads only dp[i-1][j] (row above, already filled) and dp[i][j-1] (same row, already filled this pass). Top-to-bottom, left-to-right satisfies both — no recursion, so Python's stack limit is irrelevant.

Space compression. Because row i depends only on row i-1 and the current row's left cell, a single rolling array of length n suffices: when you process cell j, row[j] still holds the value from the row above (the 'up') and row[j-1] holds the freshly updated 'left'. Set row[j] = 0 for obstacles. That drops space from O(m·n) to O(n).

No-obstacle aside. Without any blocks the answer is the binomial C(m+n-2, m-1) — worth mentioning, but obstacles break the closed form, which is exactly why DP earns its place.

B · Visual dry run

Interactive dry run

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

grid = [[0,0,0],[0,1,0],[0,0,0]]

Live grid state

Cells change as the traversal moves

row 0

00,0

00,1

00,2

01,0

11,1

01,2

02,0

02,1

02,2

Current traversalVisited / sunkUnvisited land

[1, 1, 1] (all free, left-propagated)

Final result2

C · Code with teaching comments

solution.javaJava

Bottom-Up — Grid Table, Rolling Row (Optimal) — optimal

4 teaching notes

1
public int uniquePathsWithObstacles(int[][] grid) {
2
    int m = grid.length, n = grid[0].length;
3
    long[] row = new long[n];
4
    // The start seeds 1 path only when it's not an obstacle — the most common slip.
5
    row[0] = (grid[0][0] == 0) ? 1 : 0;  // seed only if start is free
6
    for (int j = 1; j < n; j++) {
7
        // First row: one incoming direction; an obstacle zeroes everything after it.
8
        row[j] = (grid[0][j] == 1) ? 0 : row[j - 1];
9
    }
10
    for (int i = 1; i < m; i++) {
11
        if (grid[i][0] == 1) {
12
            row[0] = 0;                  // obstacle kills the rest of the column
13
        }
14
        for (int j = 1; j < n; j++) {
15
            if (grid[i][j] == 1) {
16
                row[j] = 0;
17
            } else {
18
                // row[j] still holds the row-above value (up); row[j-1] is the
19
                // just-updated left.
20
                row[j] = row[j] + row[j - 1]; // up (old row[j]) + left
21
            }
22
        }
23
    }
24
    return (int) row[n - 1];
25
}

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

D · Why it works and complexityO(m·n) timeO(n) with a rolling row spaceOpen the invariant and proofExplore the proof

This is the canonical grid counting DP: each cell sums its in-edges (up + left), a blocked cell is a 0, fill in dependency order, then compress to one row. The same skeleton powers Unique Paths (no obstacles), Minimum Path Sum (min instead of sum), and Dungeon Game (reverse sweep).

ComplexityO(m·n) time, O(n) with a rolling row space — Filling m·n cells with O(1) work each is O(m·n) time. Each row needs only the previous row's values, so one rolling array of length n gives O(n) space.

E · Edge cases and pitfalls6blocked start — row[0] seeded to 0 → entire grid stays 0 → answer 0.Explore edge cases

Edge cases handled

blocked startrow[0] seeded to 0 → entire grid stays 0 → answer 0.
obstacle across an entire rowNo cell below is reachable from above past that row → end cell 0.
1×n or m×1 gridSingle line of cells; any obstacle blocks the only path → 0, else 1.

Pitfalls

Seeding dp[0][0] = 1 without checking the start is free.
Initializing the whole first row/column to 1 — ignores obstacles that should zero the rest of the line.
Adding the left neighbour into a blocked cell instead of forcing it to 0 — leaks paths through walls.

Practice

Try the solution yourself

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

Editable code previewpublic int uniquePathsWithObstacles(int[][] grid) { int m = grid.length, n = grid[0].length; long[] row = new long[n]; row[0] = (grid[0][0] == 0) ? 1 : 0; // seed only if start is free for (int j = 1; j < n; j++) {Explore the playground

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

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Unconditional start seed

If grid[0][0] is an obstacle there are zero paths, but hard-coding dp[0][0] = 1 reports phantom routes that start on a wall.

Explore the code comparison

Don't write this

dp[0][0] = 1                      # ignores a blocked start

Write this instead

dp[0][0] = 1 if grid[0][0] == 0 else 0

Blanket first row/column = 1

The first row/column have one incoming direction, so an obstacle there zeroes every later cell on that line. Setting them all to 1 over-counts paths that actually run into a wall.

Explore the code comparison

Don't write this

for (int j = 0; j < n; j++) dp[0][j] = 1;   // ignores obstacles in row 0

Write this instead

dp[0][0] = grid[0][0] == 0 ? 1 : 0;
for (int j = 1; j < n; j++) {
    dp[0][j] = grid[0][j] == 1 ? 0 : dp[0][j - 1];
}

Blocked cell still sums predecessors

If you compute up + left for an obstacle cell, paths leak through the wall and propagate. A blocked cell must be a hard 0 regardless of its neighbours.

Explore the code comparison

Don't write this

row[j] = row[j] + row[j - 1]      # runs even when grid[i][j] == 1

Write this instead

if grid[i][j] == 1:
    row[j] = 0
else:
    row[j] = row[j] + row[j - 1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Grid DP — paths into a cell = paths from above + paths from the left

Code pattern to memorize

if grid[i][j] is blocked: dp[i][j] = 0
elif i == 0 and j == 0: dp[i][j] = 1
else: dp[i][j] = (i>0 ? dp[i-1][j] : 0) + (j>0 ? dp[i][j-1] : 0)
answer = dp[m-1][n-1]

Rules to remember

1Moves are right or down only — so any path into (i, j) arrives from (i-1, j) (above) or (i, j-1) (left).
2A blocked cell contributes 0 paths; its dp is forced to 0 and it passes nothing on.
3Seed the start: dp[0][0] = 1 only if (0, 0) is free — a blocked start means zero total paths.
4First row / first column have a single incoming direction; an obstacle there zeroes every cell after it along that line.
5Each row depends only on the row above and the cell to the left, so you can compress to one rolling row → O(n) space.

Use this pattern when

Count (not find) the lattice paths in a grid with right/down (or monotone) moves
Cells or edges can be blocked and you must route around them
A DAG of grid cells where each cell's value sums its predecessors
Combinatorial path counting that obstacles make non-closed-form

Choose another pattern when

No obstacles and you just need the count → closed form C(m+n-2, m-1), no DP
You can move in 4 directions / revisit cells → it's a graph traversal, not a DAG DP
You need the shortest or minimum-cost path → BFS / Dijkstra / min-path-sum DP, not counting
Path count overflows → use a big integer or take a modulus

Interview takeaway

Count Paths with Obstacles is the entry-level grid DP: every cell sums the paths from above and from the left, a blocked cell is a hard 0, and the start must be free to count at all. Watch the first row and column — one obstacle there cuts off everything downstream. The same dp underlies Unique Paths, Minimum Path Sum, and Dungeon Game.

Continue

Transfer the pattern to another problem

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

Transferable patternCanonical grid counting DP on a right/down DAG. Recognise it when you count monotone lattice paths and cells can be blocked: each free cell sums the paths from above and from the left, a blocked cell is 0, and the free start seeds 1. Compress to one rolling row. Same skeleton as Unique Paths, Minimum Path Sum, and Dungeon Game.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Unique Paths
No obstacles — same DP, or the closed form C(m+n-2, m-1).
Minimum Path Sum
Same grid skeleton, but take min of up/left and add the cell's cost instead of summing counts.
Dungeon Game
Coming soon
Right/down grid DP filled in reverse — track minimum health needed to survive.
Unique Paths III
Coming soon
Must visit every free cell with 4-directional moves — switches to backtracking, not a simple DP.

Same pattern

←

Boolean Parenthesization

Continue · Next problem

Longest Palindromic Subsequence

mediumDynamic ProgrammingLC #63Frequently asked

Count Paths in a Grid with Obstacles

LCPractice

Dynamic Programming · 28 of 44 · 11 min

You are given an m × n integer grid where grid[i][j] = 0 means the cell is free and grid[i][j] = 1 means it is blocked by an obstacle.

A robot starts at the top-left cell (0, 0) and wants to reach the bottom-right cell (m-1, n-1). It can move only right or down at each step, and it cannot enter a blocked cell.

Return the **number of distinct paths** the robot can take. If the start or destination is blocked, the answer is 0.

In plain English

Examples

Example 1

Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Note: The obstacle at the center forces the two routes: right→right→down→down and down→down→right→right.

Example 2

Input: grid = [[0,1],[0,0]]
Output: 1
Note: The only path is down then right; the obstacle at (0,1) blocks the right-first route.

Example 3

Input: grid = [[1,0],[0,0]]
Output: 0
Note: The start is blocked, so no path can even begin — zero ways.

Constraints

1 ≤ m, n ≤ 100
grid[i][j] is 0 (free) or 1 (blocked)
Moves are restricted to right and down
The path count can be large but fits in a 64-bit integer for these bounds

Clarifying questions4First question: Which moves are allowed?Explore questions

Q1.Which moves are allowed?
Only right and down. That monotonicity is what makes it a clean DAG DP — a cell's only predecessors are above and to the left, so there are no cycles.
Q2.What if the start or end cell is blocked?
Then there are zero paths. A blocked start makes dp[0][0] = 0, which propagates; a blocked end makes dp[m-1][n-1] = 0 directly.
Q3.Can a path revisit a cell?
No — with only right/down moves you always make progress toward the corner, so cells are never revisited. That's why it's a counting DP, not a search.
Q4.Could the count overflow?
For 100×100 the count can be astronomically large in theory, but the obstacle version stays within 64-bit for the given bounds. If asked, I'd switch to a big integer or a modulus.

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 set up dp[i][j] = dp[i-1][j] + dp[i][j-1], force blocked cells to 0, seed the start correctly, and handle obstacles in the first row/column that zero out the rest of that line.

Where candidates slip

Hard-coding dp[0][0] = 1 without checking the start is free, initializing the whole first row/column to 1 ignoring obstacles, or counting a blocked cell as passable.

How to stand out

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	Brute Force — Recursion Over Right/Down Choices	`O(2^(m+n))`	`O(m + n)`	Say this first to establish the 'paths = from above + from left' recurrence and the obstacle/boundary rules, then flag the exponential branching.	Read
2	Top-Down Memoization on (i, j)	`O(m·n)`	`O(m·n)`	The fix once you name the overlap — 'cache solve(i, j) so each cell is computed once'.	Read
3	Bottom-Up — Grid Table, Rolling Row (Optimal)Optimal	`O(m·n)`	`O(n) with a rolling row`	The answer they want. Frame it as 'dp[i][j] = up + left, sweep row by row', then compress to one row.	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 3

Brute Force — Recursion Over Right/Down Choices

TimeO(2^(m+n))SpaceO(m + n)

Say this first to establish the 'paths = from above + from left' recurrence and the obstacle/boundary rules, then flag the exponential branching.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At each free cell you can go right or down. How many ways reach a given cell? Sum the ways that reach the cells you could have stepped from.

2Hint 2Explore hint

Define solve(i, j) = number of paths from the start to cell (i, j). It comes from the cell above and the cell to the left.

3Hint 3Explore hint

Base cases: a blocked cell has 0 paths; the start (0,0) has 1 if free. Out-of-bounds predecessors contribute 0.

A · Core idea

Define solve(i, j) = the number of distinct right/down paths from the start (0, 0) to cell (i, j).

If (i, j) is blocked, no path can be on it → 0.
If (i, j) is the start and it's free → 1 (the empty path).
Otherwise sum the paths arriving from the only two cells you could have stepped from: above solve(i-1, j) (if i > 0) and left solve(i, j-1) (if j > 0).

B · Visual dry run

Interactive dry run

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

grid = [[0,0],[0,0]] (no obstacles, 2×2)

Live grid state

Cells change as the traversal moves

solve(0,0)

00,0

00,1

01,0

01,1

Current traversalVisited / sunkUnvisited land

free start

Final result2

C · Code with teaching comments

Reference implementation previewpublic int uniquePathsWithObstacles(int[][] grid) { int m = grid.length, n = grid[0].length; return solve(grid, m - 1, n - 1); } Explore the full code

solution.javaJava

Brute Force — Recursion Over Right/Down Choices — reference

3 teaching notes

1
public int uniquePathsWithObstacles(int[][] grid) {
2
    int m = grid.length, n = grid[0].length;
3
    return solve(grid, m - 1, n - 1);
4
}
5
 
6
// paths from (0,0) to (i,j)
7
private int solve(int[][] grid, int i, int j) {
8
    // Out-of-bounds or blocked → 0 paths. Folds the boundary and obstacle cases into
9
    // one guard.
10
    if (i < 0 || j < 0 || grid[i][j] == 1) {
11
        return 0;
12
    }
13
    // The free start is the single seed of 1 path.
14
    if (i == 0 && j == 0) {
15
        return 1;
16
    }
17
    // Paths arriving from above plus paths arriving from the left.
18
    return solve(grid, i - 1, j) + solve(grid, i, j - 1);
19
}

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

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

The state is the cell (i, j) and the recursion revisits the same cell through many path prefixes. A 2-D grid state plus exponential overlap is the textbook signal for an O(m·n) DP.

E · Edge cases and pitfalls5blocked start — grid[0][0] == 1 → solve returns 0 immediately.Explore edge cases

Edge cases handled

blocked startgrid[0][0] == 1 → solve returns 0 immediately.
1×1 free gridStart equals end and is free → 1 path.

Pitfalls

Returning 1 for out-of-bounds predecessors instead of 0 — over-counts along the borders.
Forgetting the obstacle check before the start check — a blocked start would wrongly return 1.
Skipping this approach — the 'sum of two predecessors' recurrence is what the interviewer wants verbalized.

03.2

Approach 2 of 3

Top-Down Memoization on (i, j)

TimeO(m·n)SpaceO(m·n)

The fix once you name the overlap — 'cache solve(i, j) so each cell is computed once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

solve(i, j) returns the same count every call. Where can you store it so each cell is computed once?

2Hint 2Explore hint

Use a 2-D memo of size m × n. Mark cells 'uncomputed' with -1 (real counts are ≥ 0), check on entry, store before returning.

3Hint 3Explore hint

There are O(m·n) cells and each does O(1) work → O(m·n) time and space.

A · Core idea

Keep the 'sum of two predecessors' recurrence but cache solve(i, j) so each cell is computed once.

B · Visual dry run

Interactive dry run

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

grid = [[0,0,0],[0,1,0],[0,0,0]]

Live grid state

Cells change as the traversal moves

top row & left col

00,0

00,1

00,2

01,0

11,1

01,2

02,0

02,1

02,2

Current traversalVisited / sunkUnvisited land

all reachable cells cache 1 (single direction in)

Final result2

C · Code with teaching comments

solution.javaJava

Top-Down Memoization on (i, j) — reference

3 teaching notes

1
public int uniquePathsWithObstacles(int[][] grid) {
2
    int m = grid.length, n = grid[0].length;
3
    // null marks 'uncomputed' — a free start returns 1, so 0 can't mean empty.
4
    Integer[][] memo = new Integer[m][n];
5
    return solve(grid, m - 1, n - 1, memo);
6
}
7
 
8
private int solve(int[][] grid, int i, int j, Integer[][] memo) {
9
    if (i < 0 || j < 0 || grid[i][j] == 1) {
10
        return 0;
11
    }
12
    if (i == 0 && j == 0) {
13
        return 1;
14
    }
15
    // Cache hit returns the stored count in O(1).
16
    if (memo[i][j] != null) {
17
        return memo[i][j];
18
    }
19
    // Store the summed predecessors before returning so the cell is never recomputed.
20
    memo[i][j] = solve(grid, i - 1, j, memo) + solve(grid, i, j - 1, memo);
21
    return memo[i][j];
22
}

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

D · Why it works and complexityO(m·n) timeO(m·n) spaceOpen the invariant and proofExplore the proof

Standard DP upgrade: the correct recurrence plus a cache keyed on the cell (i, j). The thinking — two predecessors, obstacle = 0, free start = 1 — was done in the brute force.

E · Edge cases and pitfalls5obstacle blocking all routes — Every path to the end passes a blocked cell → end cell caches 0.Explore edge cases

Edge cases handled

obstacle blocking all routesEvery path to the end passes a blocked cell → end cell caches 0.
large grid in PythonDepth m+n may near the recursion limit; raise it or use the table.

Pitfalls

Using 0 as the sentinel — a free start returns 1 and blocked cells return 0, so 0 is a real value; use null/-1.
Checking the start base case before the obstacle guard — a blocked start would wrongly return 1.
Deep recursion in Python on tall/wide grids — tabulation avoids the stack.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Grid Table, Rolling Row (Optimal)

TimeO(m·n)SpaceO(n) with a rolling row

The answer they want. Frame it as 'dp[i][j] = up + left, sweep row by row', then compress to one row.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp[i][j] = number of paths to cell (i, j). Fill row by row, left to right, so the cell above and the cell to the left are already done.

2Hint 2Explore hint

Seed dp[0][0] = 1 if the start is free, else 0. A blocked cell sets dp[i][j] = 0; otherwise dp[i][j] = up + left (treat off-grid as 0).

3Hint 3Explore hint

Since row i depends only on row i-1 and the cell to its left, keep a single rolling row of length n → O(n) space. Answer is the last cell.

A · Core idea

No-obstacle aside. Without any blocks the answer is the binomial C(m+n-2, m-1) — worth mentioning, but obstacles break the closed form, which is exactly why DP earns its place.

B · Visual dry run

Interactive dry run

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

grid = [[0,0,0],[0,1,0],[0,0,0]]

Live grid state

Cells change as the traversal moves

row 0

00,0

00,1

00,2

01,0

11,1

01,2

02,0

02,1

02,2

Current traversalVisited / sunkUnvisited land

[1, 1, 1] (all free, left-propagated)

Final result2

C · Code with teaching comments

solution.javaJava

Bottom-Up — Grid Table, Rolling Row (Optimal) — optimal

4 teaching notes

1
public int uniquePathsWithObstacles(int[][] grid) {
2
    int m = grid.length, n = grid[0].length;
3
    long[] row = new long[n];
4
    // The start seeds 1 path only when it's not an obstacle — the most common slip.
5
    row[0] = (grid[0][0] == 0) ? 1 : 0;  // seed only if start is free
6
    for (int j = 1; j < n; j++) {
7
        // First row: one incoming direction; an obstacle zeroes everything after it.
8
        row[j] = (grid[0][j] == 1) ? 0 : row[j - 1];
9
    }
10
    for (int i = 1; i < m; i++) {
11
        if (grid[i][0] == 1) {
12
            row[0] = 0;                  // obstacle kills the rest of the column
13
        }
14
        for (int j = 1; j < n; j++) {
15
            if (grid[i][j] == 1) {
16
                row[j] = 0;
17
            } else {
18
                // row[j] still holds the row-above value (up); row[j-1] is the
19
                // just-updated left.
20
                row[j] = row[j] + row[j - 1]; // up (old row[j]) + left
21
            }
22
        }
23
    }
24
    return (int) row[n - 1];
25
}

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

D · Why it works and complexityO(m·n) timeO(n) with a rolling row spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6blocked start — row[0] seeded to 0 → entire grid stays 0 → answer 0.Explore edge cases

Edge cases handled

blocked startrow[0] seeded to 0 → entire grid stays 0 → answer 0.
obstacle across an entire rowNo cell below is reachable from above past that row → end cell 0.
1×n or m×1 gridSingle line of cells; any obstacle blocks the only path → 0, else 1.

Pitfalls

Seeding dp[0][0] = 1 without checking the start is free.
Initializing the whole first row/column to 1 — ignores obstacles that should zero the rest of the line.
Adding the left neighbour into a blocked cell instead of forcing it to 0 — leaks paths through walls.

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

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Unconditional start seed

If grid[0][0] is an obstacle there are zero paths, but hard-coding dp[0][0] = 1 reports phantom routes that start on a wall.

Explore the code comparison

Don't write this

dp[0][0] = 1                      # ignores a blocked start

Write this instead

dp[0][0] = 1 if grid[0][0] == 0 else 0

Blanket first row/column = 1

The first row/column have one incoming direction, so an obstacle there zeroes every later cell on that line. Setting them all to 1 over-counts paths that actually run into a wall.

Explore the code comparison

Don't write this

for (int j = 0; j < n; j++) dp[0][j] = 1;   // ignores obstacles in row 0

Write this instead

dp[0][0] = grid[0][0] == 0 ? 1 : 0;
for (int j = 1; j < n; j++) {
    dp[0][j] = grid[0][j] == 1 ? 0 : dp[0][j - 1];
}

Blocked cell still sums predecessors

If you compute up + left for an obstacle cell, paths leak through the wall and propagate. A blocked cell must be a hard 0 regardless of its neighbours.

Explore the code comparison

Don't write this

row[j] = row[j] + row[j - 1]      # runs even when grid[i][j] == 1

Write this instead

if grid[i][j] == 1:
    row[j] = 0
else:
    row[j] = row[j] + row[j - 1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Grid DP — paths into a cell = paths from above + paths from the left

Code pattern to memorize

if grid[i][j] is blocked: dp[i][j] = 0
elif i == 0 and j == 0: dp[i][j] = 1
else: dp[i][j] = (i>0 ? dp[i-1][j] : 0) + (j>0 ? dp[i][j-1] : 0)
answer = dp[m-1][n-1]

Rules to remember

1Moves are right or down only — so any path into (i, j) arrives from (i-1, j) (above) or (i, j-1) (left).
2A blocked cell contributes 0 paths; its dp is forced to 0 and it passes nothing on.
3Seed the start: dp[0][0] = 1 only if (0, 0) is free — a blocked start means zero total paths.
4First row / first column have a single incoming direction; an obstacle there zeroes every cell after it along that line.
5Each row depends only on the row above and the cell to the left, so you can compress to one rolling row → O(n) space.

Use this pattern when

Count (not find) the lattice paths in a grid with right/down (or monotone) moves
Cells or edges can be blocked and you must route around them
A DAG of grid cells where each cell's value sums its predecessors
Combinatorial path counting that obstacles make non-closed-form

Choose another pattern when

No obstacles and you just need the count → closed form C(m+n-2, m-1), no DP
You can move in 4 directions / revisit cells → it's a graph traversal, not a DAG DP
You need the shortest or minimum-cost path → BFS / Dijkstra / min-path-sum DP, not counting
Path count overflows → use a big integer or take a modulus

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

Unique Paths
No obstacles — same DP, or the closed form C(m+n-2, m-1).
Minimum Path Sum
Same grid skeleton, but take min of up/left and add the cell's cost instead of summing counts.
Dungeon Game
Coming soon
Right/down grid DP filled in reverse — track minimum health needed to survive.
Unique Paths III
Coming soon
Must visit every free cell with 4-directional moves — switches to backtracking, not a simple DP.

Same pattern

←

Boolean Parenthesization

Continue · Next problem

Longest Palindromic Subsequence