Unique Paths II
MedPrompt
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 -> RightExample 2:
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Constraints:
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]is0or1.
Approaches
5 approaches with complexity analysis and trade-offs.
This approach optimizes the 2D DP solution's space complexity. Since calculating the number of paths for the current row only requires values from the current and previous row, we can use a single 1D array to store the DP values, reducing space from O(m*n) to O(n).
Algorithm
- Get grid dimensions
mandn. - If
obstacleGrid[0][0] == 1, return 0. - Create a 1D DP array
dpof sizen. - Initialize
dp[0] = 1. - Iterate through rows
ifrom 0 tom-1: a. Iterate through columnsjfrom 0 ton-1: i. IfobstacleGrid[i][j] == 1, setdp[j] = 0. ii. Else ifj > 0, updatedp[j] = dp[j] + dp[j-1]. - Return
dp[n-1].
Walkthrough
We use a 1D array dp of size n. dp[j] will represent the number of paths to reach the cell in the current row at column j.
We iterate through the grid row by row. For each row i, we update the dp array. The update rule dp[j] = dp[j] + dp[j-1] works because when we are at (i, j), dp[j] still holds the value from the previous row (i-1, j), and dp[j-1] has just been updated to hold the value for (i, j-1).
- Initialization:
- Create a
dparray of sizen. - If
obstacleGrid[0][0] == 1, return 0. Otherwise, setdp[0] = 1.
- Create a
- Iteration:
- Iterate through rows
ifrom 0 tom-1. - For each row, iterate through columns
jfrom 0 ton-1. - If
obstacleGrid[i][j] == 1, there are no paths to this cell, so setdp[j] = 0. - If
j > 0, add the paths from the left cell:dp[j] += dp[j-1]. - Note: For the first cell of each row (
j=0), if it's an obstacle,dp[0]becomes 0. If not, it retains its value from the previous row, which is correct as it can only be reached from above.
- Iterate through rows
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; if (obstacleGrid[0][0] == 1) { return 0; } int[] dp = new int[n]; dp[0] = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[j] = 0; } else if (j > 0) { dp[j] = dp[j] + dp[j - 1]; } } } return dp[n - 1]; }}Complexity
Time
O(m*n)
Space
O(n)
Trade-offs
Pros
Highly efficient in both time and space.
Optimal space complexity among solutions that do not modify the input.
Cons
The logic can be slightly less intuitive than the 2D DP approach.
The 1D array is overwritten, so we lose the path counts for previous rows.
This is the most space-efficient approach, using the input grid itself as the DP table. It modifies the grid to store the number of paths to each cell, thus achieving O(1) extra space complexity. This is feasible if modifying the input is allowed.
Algorithm
- Get grid dimensions
mandn. - If
obstacleGrid[0][0] == 1, return 0. - Set
obstacleGrid[0][0] = 1(to represent 1 path). - Fill the first column: For
ifrom 1 tom-1, setobstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i-1][0] == 1) ? 1 : 0. - Fill the first row: For
jfrom 1 ton-1, setobstacleGrid[0][j] = (obstacleGrid[0][j] == 0 && obstacleGrid[0][j-1] == 1) ? 1 : 0. - Iterate from
i = 1tom-1andj = 1ton-1: a. IfobstacleGrid[i][j] == 1(original obstacle), set its path count to 0. b. Else,obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]. - Return
obstacleGrid[m-1][n-1].
Walkthrough
The core idea is to use the obstacleGrid to store the DP values. A cell obstacleGrid[i][j] is updated to hold the number of unique paths to reach it. This eliminates the need for any auxiliary data structure.
- First, we handle the starting cell
(0,0). If it's an obstacle (value 1), no path is possible, so we return 0. Otherwise, we setobstacleGrid[0][0] = 1to signify one way to reach the start (by starting there). - Next, we process the first column. A cell
(i, 0)is reachable only if it's not an obstacle and the cell above it(i-1, 0)was reachable. We updateobstacleGrid[i][0]to 1 if these conditions hold, and 0 otherwise. - We do the same for the first row. A cell
(0, j)is reachable only if it's not an obstacle and the cell to its left(0, j-1)was reachable. - Finally, we iterate through the rest of the grid. For any cell
(i, j), if it's an obstacle, the number of paths to it is 0. Otherwise, it's the sum of paths from the cell above (obstacleGrid[i-1][j]) and the cell to the left (obstacleGrid[i][j-1]). - The final answer is the value stored in the bottom-right cell,
obstacleGrid[m-1][n-1].
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; // If the starting cell has an obstacle, then simply return 0 if (obstacleGrid[0][0] == 1) { return 0; } // Number of ways of reaching the starting cell = 1 obstacleGrid[0][0] = 1; // Filling the values for the first column for (int i = 1; i < m; i++) { obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0; } // Filling the values for the first row for (int j = 1; j < n; j++) { obstacleGrid[0][j] = (obstacleGrid[0][j] == 0 && obstacleGrid[0][j - 1] == 1) ? 1 : 0; } // Starting from cell(1,1) fill up the values for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 0) { obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; } else { obstacleGrid[i][j] = 0; } } } // Return value stored in rightmost bottommost cell. return obstacleGrid[m - 1][n - 1]; }}Complexity
Time
O(m*n)
Space
O(1)
Trade-offs
Pros
Most space-efficient solution with O(1) extra space.
Maintains the optimal O(m*n) time complexity.
Cons
Modifies the input array, which might be undesirable in some contexts.
The logic for handling the first row/column and distinguishing obstacles from path counts can be tricky to implement correctly.
This approach directly translates the problem into a recursive function. For any given cell, the number of paths is the sum of paths from the cell below and the cell to the right. We explore all possible paths from the start to the end, but this leads to an exponential number of redundant calculations.
Algorithm
- Define a recursive function
solve(row, col, grid). - Check for base cases:
a. If
roworcolare out of bounds, or ifgrid[row][col] == 1, return 0. b. Ifrowandcolpoint to the destination(m-1, n-1), return 1. - Recursively call the function for the next possible moves:
a.
paths_down = solve(row + 1, col, grid)b.paths_right = solve(row, col + 1, grid) - Return the sum
paths_down + paths_right. - The main function calls
solve(0, 0, obstacleGrid).
Walkthrough
We define a recursive helper function, say countPaths(row, col), which calculates the number of unique paths from the current cell (row, col) to the destination (m-1, n-1). The function has the following logic:
- Base Cases:
- If the current cell
(row, col)is an obstacle (obstacleGrid[row][col] == 1), no paths can pass through it, so we return 0. - If the current cell is the destination
(m-1, n-1), we have found one valid path, so we return 1. - If the current cell is out of the grid boundaries, it's an invalid path, so we return 0.
- If the current cell
- Recursive Step:
- For any other cell, the number of paths is the sum of the paths from moving down (
countPaths(row + 1, col)) and the paths from moving right (countPaths(row, col + 1)).
- For any other cell, the number of paths is the sum of the paths from moving down (
The initial call to the function will be countPaths(0, 0). This method is simple but highly inefficient because it recalculates the number of paths for the same cells multiple times.
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; // Need to handle the case where the destination itself is an obstacle if (obstacleGrid[m - 1][n - 1] == 1) return 0; return countPaths(0, 0, m, n, obstacleGrid); } private int countPaths(int row, int col, int m, int n, int[][] obstacleGrid) { // If out of bounds or on an obstacle, there are no paths. if (row >= m || col >= n || obstacleGrid[row][col] == 1) { return 0; } // If we reached the destination, we found one path. if (row == m - 1 && col == n - 1) { return 1; } // Recursively find paths by moving down and right. int pathsDown = countPaths(row + 1, col, m, n, obstacleGrid); int pathsRight = countPaths(row, col + 1, m, n, obstacleGrid); return pathsDown + pathsRight; }}Complexity
Time
O(2^(m+n))
Space
O(m + n)
Trade-offs
Pros
Simple to understand and implement.
Directly translates the problem's recursive nature.
Cons
Extremely inefficient due to recomputing the same subproblems.
Will result in a "Time Limit Exceeded" (TLE) error for larger grids.
This approach optimizes the brute-force recursion by using a memoization table (a 2D array) to store the results of subproblems. This technique, also known as top-down dynamic programming, avoids redundant computations for the same cell, drastically improving performance.
Algorithm
- Create a 2D array
memoof sizem x nand initialize all its values to -1. - Define a function
solve(row, col, grid, memo). - Check for base cases:
a. If
roworcolare out of bounds, or ifgrid[row][col] == 1, return 0. b. Ifrowandcolpoint to the destination(m-1, n-1), return 1. - Check the memoization table: If
memo[row][col]is not -1, return its value. - Recursively call the function for the next possible moves:
a.
paths_down = solve(row + 1, col, grid, memo)b.paths_right = solve(row, col + 1, grid, memo) - Store the result
paths_down + paths_rightinmemo[row][col]. - Return the stored result.
- The main function calls
solve(0, 0, obstacleGrid, memo).
Walkthrough
We enhance the recursive solution by adding a cache, typically a 2D array memo, of the same dimensions as the grid. memo[i][j] will store the number of unique paths from cell (i, j) to the destination.
The memo table is initialized with a special value (e.g., -1) to indicate that a state has not been computed yet. In the recursive function countPaths(row, col), before any computation, we first check if memo[row][col] has a value other than -1. If it does, we return the stored value directly. Otherwise, we compute the result as in the brute-force approach, and before returning, we store the result in memo[row][col]. This ensures that the number of paths for each cell is calculated only once.
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] memo = new int[m][n]; for (int[] row : memo) { java.util.Arrays.fill(row, -1); } // Need to handle the case where the destination itself is an obstacle if (obstacleGrid[m - 1][n - 1] == 1) return 0; return countPaths(0, 0, m, n, obstacleGrid, memo); } private int countPaths(int row, int col, int m, int n, int[][] obstacleGrid, int[][] memo) { if (row >= m || col >= n || obstacleGrid[row][col] == 1) { return 0; } if (row == m - 1 && col == n - 1) { return 1; } if (memo[row][col] != -1) { return memo[row][col]; } int pathsDown = countPaths(row + 1, col, m, n, obstacleGrid, memo); int pathsRight = countPaths(row, col + 1, m, n, obstacleGrid, memo); memo[row][col] = pathsDown + pathsRight; return memo[row][col]; }}Complexity
Time
O(m*n)
Space
O(m*n)
Trade-offs
Pros
Much more efficient than brute-force recursion.
Avoids TLE for the given constraints.
Maintains a clear, top-down recursive structure.
Cons
Uses O(m*n) extra space for the memoization table.
Can lead to stack overflow for very deep recursion, though not an issue for the given constraints.
This is an iterative, bottom-up dynamic programming approach. We use a 2D DP table to store the number of unique paths to reach each cell. The value of a cell (i, j) is calculated based on the sum of paths to the cell above (i-1, j) and the cell to its left (i, j-1).
Algorithm
- Get grid dimensions
mandn. - If
obstacleGrid[0][0] == 1, return 0. - Create a 2D DP array
dp[m][n]. - Set
dp[0][0] = 1. - Fill the first column: For
ifrom 1 tom-1,dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0. - Fill the first row: For
jfrom 1 ton-1,dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0. - Iterate from
i = 1tom-1andj = 1ton-1: a. IfobstacleGrid[i][j] == 1, setdp[i][j] = 0. b. Else,dp[i][j] = dp[i-1][j] + dp[i][j-1]. - Return
dp[m-1][n-1].
Walkthrough
We create a 2D array dp of size m x n, where dp[i][j] will store the number of unique paths from the start (0, 0) to the cell (i, j). The state transition is dp[i][j] = dp[i-1][j] + dp[i][j-1].
- Initialization:
- First, check if the start cell is an obstacle. If
obstacleGrid[0][0] == 1, no path is possible, so return 0. - Set
dp[0][0] = 1as there is one way to be at the starting cell. - Initialize the first row: For
jfrom 1 ton-1,dp[0][j]can only be reached fromdp[0][j-1]. IfobstacleGrid[0][j]is an obstacle ordp[0][j-1]is 0, thendp[0][j]is 0. Otherwise, it's 1. - Initialize the first column similarly.
- First, check if the start cell is an obstacle. If
- Iteration:
- Iterate from
i = 1tom-1andj = 1ton-1. - For each cell
(i, j), if it's an obstacle (obstacleGrid[i][j] == 1), setdp[i][j] = 0. - Otherwise, calculate
dp[i][j] = dp[i-1][j] + dp[i][j-1].
- Iterate from
The final result is the value in the bottom-right cell of the DP table, dp[m-1][n-1].
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; if (obstacleGrid[0][0] == 1) { return 0; } int[][] dp = new int[m][n]; dp[0][0] = 1; // Fill first column for (int i = 1; i < m; i++) { if (obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1) { dp[i][0] = 1; } else { dp[i][0] = 0; } } // Fill first row for (int j = 1; j < n; j++) { if (obstacleGrid[0][j] == 0 && dp[0][j - 1] == 1) { dp[0][j] = 1; } else { dp[0][j] = 0; } } // Fill the rest of the grid for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[i][j] = 0; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; }}Complexity
Time
O(m*n)
Space
O(m*n)
Trade-offs
Pros
Efficient and avoids recursion overhead.
Generally faster in practice than memoization due to being iterative.
Cons
Requires O(m*n) extra space, which can be optimized.
Solutions
Solution
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length, n = obstacleGrid[0].length; int[][] dp = new int[m][n]; for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) { dp[i][0] = 1; } for (int j = 0; j < n && obstacleGrid[0][j] == 0; ++j) { dp[0][j] = 1; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (obstacleGrid[i][j] == 0) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; }}/** * @param {number[][]} obstacleGrid * @return {number} */ var uniquePathsWithObstacles = function (obstacleGrid) { const m = obstacleGrid.length; const n = obstacleGrid[0].length; const f = Array.from({ length: m }, () => Array(n).fill(-1)); const dfs = (i, j) => { if (i >= m || j >= n || obstacleGrid[i][j] === 1) { return 0; } if (i === m - 1 && j === n - 1) { return 1; } if (f[i][j] === -1) { f[i][j] = dfs(i + 1, j) + dfs(i, j + 1); } return f[i][j]; }; return dfs(0, 0); };class Solution {public: int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector<vector<int>> dp(m, vector<int>(n)); for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) { dp[i][0] = 1; } for (int j = 0; j < n && obstacleGrid[0][j] == 0; ++j) { dp[0][j] = 1; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (obstacleGrid[i][j] == 0) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; }};class Solution: # dp[1][1] = dp[0][1] + dp[1][0] # so, set either dp[0][1]=1, or set dp[1][0]=1 dp [ 0 ][ 1 ] = 1 for i in range ( 1 , m + 1 ): for j in range ( 1 , n + 1 ): if obstacleGrid [ i - 1 ][ j - 1 ] == 0 : dp [ i ][ j ] = dp [ i - 1 ][ j ] + dp [ i ][ j - 1 ] # else, ==1, obstacle, skip and leave as 0 return dp [ m ][ n ] ############ class Solution : def uniquePathsWithObstacles ( self , obstacleGrid : List [ List [ int ]]) -> int : m , n = len ( obstacleGrid ), len ( obstacleGrid [ 0 ]) dp = [[ 0 ] * n for _ in range ( m )] for i in range ( m ): if obstacleGrid [ i ][ 0 ] == 1 : break dp [ i ][ 0 ] = 1 for j in range ( n ): if obstacleGrid [ 0 ][ j ] == 1 : break dp [ 0 ][ j ] = 1 for i in range ( 1 , m ): for j in range ( 1 , n ): if obstacleGrid [ i ][ j ] == 0 : dp [ i ][ j ] = dp [ i - 1 ][ j ] + dp [ i ][ j - 1 ] return dp [ - 1 ][ - 1 ] def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: if not obstacleGrid: return 0 m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [[0] * (n + 1) for _ in range(m + 1)]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.