Unique Paths II

Medium#632d table

A grid has free cells (0) and rocks (1). A robot starts in the top-left corner and steps only right or down, never onto a rock. Count the routes to the bottom-right corner. Our example: [0, 0, 1, 0], [0, 0, 0, 0], [0, 1, 0, 0], 4 paths.

63 Unique Paths IIWalkthrough · 1×

Example: a 3 × 4 grid with rocks at (0, 2) and (2, 1). Watch (0, 3): no rock there, yet 0 paths, because the rock before it cuts the top row. And (2, 2): its paths all come from above.

0123012✕✕
emptypaths into this cellrockthis stepread fromanswer

An empty table the size of the grid, 3 × 4; the rocks are at (0, 2) and (2, 1)

01/38
restart · back · play · step
Speed
1function uniquePathsWithObstacles(grid):
2 dp = table of the grid's size
3 for r from 0 to rows - 1:
4 for c from 0 to cols - 1:
5 if grid[r][c] == 1:
6 dp[r][c] = 0 // a rock: no path ends here
7 else if r == 0 and c == 0:
8 dp[r][c] = 1
9 else:
10 up = dp[r - 1][c] if r > 0 else 0
11 left = dp[r][c - 1] if c > 0 else 0
12 dp[r][c] = up + left
13 return dp[rows - 1][cols - 1]
state
dp
[[–, –, –, –], [–, –, –, –], [–, –, –, –]]
r
–
c
–
up
–
left
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The paths into a free cell are the paths into the cell above plus the paths into the cell to the left, as without rocks: the last move comes from one of them.
  2. A rock holds 0, so it adds nothing to the cells after it. That alone removes every path through a rock; no path has to be checked.
  3. The edges are not all ones any more: along the top row only one straight line leads in, and after a rock it is cut, so (0, 3) gets 0.

Complexity

Time O(m × n): each cell is one check and one addition. Memory O(m × n) for the table, or one row of n cells, since a cell reads only its row and the row above.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.