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: You are given an m x n grid where some cells contain obstacles. Starting at the top‑left corner, you can only move right or down. The task is to count how many unique paths reach the bottom‑right corner while avoiding obstacle cells.
Approach 1: Dynamic Programming with 2D Table (O(m*n) time, O(m*n) space)
This approach builds a dp matrix where dp[i][j] represents the number of ways to reach cell (i, j). If the current cell contains an obstacle, the value becomes 0 because no path can pass through it. Otherwise, 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]. Initialize the first row and first column carefully because obstacles block all cells after them. This solution mirrors the grid structure, making it easy to reason about transitions in dynamic programming problems.
Approach 2: Space Optimized Dynamic Programming (O(m*n) time, O(n) space)
The full m x n DP table is not required because each state only depends on the current row and the previous row. Maintain a single array of size n representing the number of ways to reach each column in the current row. When iterating through the grid, set the value to 0 if an obstacle appears. Otherwise update the current cell using dp[j] += dp[j-1], which combines paths from the top (existing value) and left (previous column). This reduces memory usage significantly while keeping the same logic based on arrays and matrix traversal.
Recommended for interviews: Interviewers usually expect the dynamic programming insight that each cell depends on its top and left neighbors. Start with the 2D DP explanation to show the recurrence clearly, then optimize it to the 1D array version. Demonstrating the space reduction from O(m*n) to O(n) shows strong understanding of DP state transitions.
Using dynamic programming, we can track the number of unique paths to each cell in the grid. Initialize a DP matrix of the same dimensions as the grid. If a cell contains an obstacle (value of 1), it will have 0 paths. Start from the top-left corner and accumulate the number of paths by adding the values from the cell above and the cell to the left, if they exist, taking into account obstacles.
This solution implements a dynamic programming strategy to fill a DP table. Each cell in the DP table represents the number of unique paths to that cell, calculated by summing the possible paths from the left and above cells, unless they contain obstacles.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), because each cell in the matrix is calculated once.
Space Complexity: O(m * n), for the DP table.
Instead of using a full 2D DP array, we can optimize space by maintaining just a single row of size `n` to hold the number of paths to positions in the current row. Iterate over the grid, and update path counts by only storing the results for the current row, using the previous row information to calculate paths.
Optimized C solution utilizes a single-dimension array to save space, updating path counts as it iterates over each grid row while handling obstacles.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), iterating through the entire grid.
Space Complexity: O(n), only a single row is stored at a time.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n), because each cell in the matrix is calculated once. |
| Space Optimized Dynamic Programming | Time Complexity: O(m * n), iterating through the entire grid. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (2D Grid) | O(m*n) | O(m*n) | Best for understanding the DP recurrence and explaining the transition clearly in interviews |
| Space Optimized DP (1D Array) | O(m*n) | O(n) | Preferred when memory is constrained or when optimizing the DP solution |
DP 9. Unique Paths 2 | DP on Grid with Maze Obstacles • take U forward • 221,148 views views
Watch 9 more video solutions →Practice Unique Paths II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor