Watch 10 video solutions for Unique Paths II, a medium level problem involving Array, Dynamic Programming, Matrix. This walkthrough by take U forward has 221,148 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right
Example 2:
Input: obstacleGrid = [[0,1],[0,0]] Output: 1
Constraints:
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] is 0 or 1.Problem Overview: Given an m x n grid where some cells contain obstacles, count how many unique paths exist from the top-left corner to the bottom-right corner. You can only move right or down, and any cell marked as an obstacle blocks the path.
Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)
This approach builds a 2D DP table where dp[i][j] stores the number of ways to reach cell (i, j). If the current cell is not an obstacle, the number of paths equals the sum of paths from the top cell dp[i-1][j] and the left cell dp[i][j-1]. If the cell contains an obstacle, its value becomes 0 because no path can pass through it. You iterate row by row through the matrix, updating the DP table using previously computed values. This approach clearly models the recurrence relation and is the easiest way to reason about the state transitions.
Approach 2: Space Optimized Dynamic Programming (O(m*n) time, O(n) space)
The DP relation only depends on the current row and the previous row, so a full m x n table is unnecessary. Instead, maintain a single array of size n where each element represents the number of ways to reach that column in the current row. While iterating through the grid, update the array in place: if a cell contains an obstacle, set the value to 0; otherwise add the value from the left neighbor dp[j] += dp[j-1]. This technique reduces memory usage while preserving the same recurrence used in dynamic programming. The logic still processes the grid row by row using standard array iteration.
Recommended for interviews: The standard 2D dynamic programming solution demonstrates clear understanding of the recurrence and boundary conditions, so it is the safest explanation during interviews. After presenting it, optimizing to a single-row DP array shows deeper understanding of memory optimization and DP state compression.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (2D DP Table) | O(m*n) | O(m*n) | Best for clarity when explaining DP state transitions during interviews |
| Space Optimized Dynamic Programming | O(m*n) | O(n) | When memory matters or when demonstrating DP state compression |