Easy Problemscountinggrid

Paths in a Grid with Obstacles

Given a grid where some cells are blocked obstacles, and starting at the top-left corner while moving only right or down at each step, count the distinct paths to the bottom-right corner that avoid every obstacle.

Do this lesson first: climbing stairs

Example input

grid = [[0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 1], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0]], where 1 marks an obstacle

Expected output

17

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[r][c] is the number of right-and-down routes from the top-left corner to cell (r, c) that never stand on an obstacle. That is the same two-number state as the unobstructed grid: the obstacles change what a cell is allowed to be, not what the cell means. Read a 0 carefully, because two different situations produce one: a blocked cell is 0 because no route may occupy it, and a clear cell is 0 when no route manages to reach it. The table prints the same digit for both, so keeping them apart is on you.

dp[r][c] = 0 if (r, c) is blocked, otherwise dp[r - 1][c] + dp[r][c - 1]

For a clear cell, ask exactly what count-all-paths-in-a-grid asks: the last step was either down from above or right from the left, the two sets of routes are disjoint, so add them. The obstacle check comes first and cancels the question entirely. If no route may stand here, there is no last step to ask about, and the count is 0 without either neighbour entering into it. Where the zero comes from is the thing to hold on to: a blocked cell is zero by rule, and a clear cell is zero only when the ways into it sum to zero, one way in along an edge and two everywhere else, which means every way in is itself dead.

dp[0][0] = 1 is the only base, and that single difference from the unobstructed grid is worth dwelling on. There the whole first row and first column can be declared 1 up front; here they cannot, because one obstacle in row 0 makes every cell to its right unreachable, so the edges have to be computed like every other cell, just with one candidate instead of two. Filling row-major keeps the cell above and the cell to the left final before they are used. A blocked cell is the one write in this table that depends on nothing at all: it has no cells to consult, so the walkthrough does not stop and ask you to predict it, because there is no arithmetic there to predict.

Tabulation over all rows times cols cells, blocked ones included, since a blocked cell still has to hold its 0 for its neighbours to add in. Memoization from the corner never visits some of them, and it pays to be exact about which: it recurses from a cell towards the start, so it skips the cells that cannot get TO the goal, which is a different set from the cells nothing can get to FROM the start. In the 5 by 5 table that means the top of column 4 goes unvisited, because the obstacle below it seals that column off from the corner, even though both of those cells are clear and hold real route counts of 1 and 2; meanwhile row 4 column 1, which nothing reaches from the start at all, does get visited, because it has a clear run right to the corner. Skipping goal-less cells is the one honest argument for going top-down here, and on a heavily walled grid it can be most of the table, though on this one it saves only three cells. The comparison across the three grid pages is the whole point of reading them together: same state, same row-major sweep, same two neighbours. count-all-paths sums them, min-cost-path adds this cell's cost to the smaller of them, and this page sums them unless the cell is blocked, in which case it is zero. One operator apart, all three.

Time O(rows × cols)Space O(rows × cols), reducible to O(cols) with one rolling row

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0][0] = 1 is the only base, and that single difference from the unobstructed grid is worth dwelling on. There the whole first row and first column can be declared 1 up front; here they cannot, because one obstacle in row 0 makes every cell to its right unreachable, so the edges have to be computed like every other cell, just with one candidate instead of two. Filling row-major keeps the cell above and the cell to the left final before they are used. A blocked cell is the one write in this table that depends on nothing at all: it has no cells to consult, so the walkthrough does not stop and ask you to predict it, because there is no arithmetic there to predict.

row r

0

1

2

3

4

0

1

2

0

1

2

1

3

4

0

3

1

0

3

7

4

0

3

10

17

column c: routes reaching (r, c)

paths-in-a-grid-with-obstacles.ts

1function countPaths(grid) {
2 const n = grid.length, m = grid[0].length;
3 const dp = Array.from({ length: n }, () => new Array(m).fill(0));
4 dp[0][0] = 1;
5 for (let r = 0; r < n; r++) {
6 for (let c = 0; c < m; c++) {
7 if (grid[r][c] === 1) { dp[r][c] = 0; continue; }
8 if (r === 0 && c === 0) continue;
9 const above = r > 0 ? dp[r - 1][c] : 0;
10 const left = c > 0 ? dp[r][c - 1] : 0;
11 dp[r][c] = above + left;
12 }
13 }
14 return dp[n - 1][m - 1];
15}

Base caseComputedBeing readAnswer

The code, the trap, the variations

paths-in-a-grid-with-obstacles.ts

1function countPaths(grid) {
2 const n = grid.length, m = grid[0].length;
3 const dp = Array.from({ length: n }, () => new Array(m).fill(0));
4 dp[0][0] = 1;
5 for (let r = 0; r < n; r++) {
6 for (let c = 0; c < m; c++) {
7 if (grid[r][c] === 1) { dp[r][c] = 0; continue; }
8 if (r === 0 && c === 0) continue;
9 const above = r > 0 ? dp[r - 1][c] : 0;
10 const left = c > 0 ? dp[r][c - 1] : 0;
11 dp[r][c] = above + left;
12 }
13 }
14 return dp[n - 1][m - 1];
15}

Where people go wrong

Reading every 0 in the table as an obstacle. In the 5 by 5 table, row 4 column 1 holds 0 and is perfectly walkable; both of its ways in are blocked, so no route reaches it, and it then hands that 0 on to its own neighbours like any ordinary value. Whole regions of clear cells can go dark like this behind a couple of well-placed obstacles. The other half of the trap is muscle memory on the edges: filling the first row and first column with 1s is right only until an obstacle appears in one of them, and seeding 1s past that obstacle invents routes that walk straight through a wall.

Ask for the cheapest route rather than the number of routes, obstacles still forbidden.
The sum becomes this cell's cost plus a min, and a blocked cell becomes infinity rather than 0, because for a minimization 0 reads as a wonderfully cheap route while infinity is what 'no route at all' means. That is min-cost-path with the obstacle rule bolted on.
Remove every obstacle.
The blocked branch never fires, row 0 and column 0 fill with 1s on their own, and the table is count-all-paths-in-a-grid again, closed form included. Drag the slider down to 2 to watch it happen: the top-left 2 by 2 corner of this grid holds no obstacle, so its answer is the unobstructed 2.
Allow yourself to bulldoze at most one obstacle of your choice.
The state gains a dimension, dp[r][c][k] with k recording whether the one removal has been spent, so the same sweep runs twice over with the k = 1 layer able to step onto a blocked cell from the k = 0 layer.

Count all paths in a Grid Permutations with K Inversions