Unique Paths II
Medium · 2-D Dynamic Programming · Array · Dynamic Programming · Matrix
Problem
A robot stands on the top-left cell of an m x n grid obstacleGrid and wants to reach the bottom-right cell. Each move takes it one cell right or one cell down.
Cells marked 1 are obstacles the robot cannot enter; cells marked 0 are free. Return the number of different paths from the top-left to the bottom-right corner that avoid every obstacle. If either corner is an obstacle, the answer is 0.
The answer always fits in a 32-bit signed integer.
Examples
Input: obstacleGrid = [[0,0,0,0],[0,1,0,0],[0,0,0,0]] Output: 4
An open 3 x 4 grid has 10 paths. The obstacle at (1, 1) sits on 6 of them, leaving 4.
Input: obstacleGrid = [[0,1],[1,0]] Output: 0
Both moves out of the start are blocked.
Input: obstacleGrid = [[0,0],[0,0]] Output: 2
Right then down, or down then right.
Constraints
- m == len(obstacleGrid), n == len(obstacleGrid[i])
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1
- The answer is at most 2 · 10^9
Approaches
- Memoized recursion from the start — time O(m · n), space O(m · n) cache plus O(m + n) recursion
Follow-up
What if the robot may also step diagonally down-right? Each cell then sums three earlier cells, and the diagonal one is the value the left neighbor had before this row overwrote it. See the use case "Paths that may also step diagonally".
Related problems
Start free on Cariara · Coding problems · System design studio
