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.
Here’s the [Problem Link] to begin with.
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]is0or1.
1. Brute Force Recursion
Intuition
- At each cell (i, j), the robot can come from above (i-1, j) or left (i, j-1) unless blocked by an obstacle.
- If a cell is an obstacle or out of bounds, it contributes zero.
- The solution sums all possible ways from the top and left.
Code
class Solution:
def solve(self, i, j, obstacleGrid):
# If at starting cell, check if it's blocked
if i == 0 and j == 0:
if obstacleGrid[0][0] == 1:
return 0
return 1
# Out of bounds
if i < 0 or j < 0:
return 0
# Obstacle at this cell
if obstacleGrid[i][j] == 1:
return 0
# Recurse up and left
up = self.solve(i - 1, j, obstacleGrid)
left = self.solve(i, j - 1, obstacleGrid)
return up + left
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
return self.solve(m - 1, n - 1, obstacleGrid)Explanation
- Recursively searches for every possible non-blocked path to (i, j).
- Returns 0 if an obstacle or outside the grid.
- Returns 1 if at the starting cell and it’s not blocked.
- Sums up all possible ways from above and left.
Complexity
- Time: O(2^(m*n)) – Each cell may try two directions, exponential growth.
- Space: O(m*n) – Recursion stack depth (call tree).
2. Memoization (Top-Down DP)
Intuition
Many cells are revisited with the same (i, j) arguments due to overlapping subproblems. Caching each (i, j) result with a DP array avoids repeated work.
Code
class Solution:
def solve(self, i, j, obstacleGrid, dp):
# If at starting cell
if i == 0 and j == 0:
if obstacleGrid[0][0] == 1:
return 0
return 1
# Out of bounds
if i < 0 or j < 0:
return 0
# Obstacle here
if obstacleGrid[i][j] == 1:
return 0
# Return cached result if already computed
if dp[i][j] != -1:
return dp[i][j]
# Compute from up and left
up = self.solve(i - 1, j, obstacleGrid, dp)
left = self.solve(i, j - 1, obstacleGrid, dp)
dp[i][j] = up + left
return dp[i][j]
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[-1 for _ in range(n)] for _ in range(m)]
return self.solve(m - 1, n - 1, obstacleGrid, dp)Explanation
- Adds a
dpmatrix to cache results for each cell. - Each (i, j) subproblem is solved only once, drastically improving speed.
- All blocked or out-of-bounds checks remain unchanged.
- The cache avoids recalculating for the same cell.
Complexity
- Time: O(m*n) – Each cell computed once.
- Space: O(m*n) – For DP table and recursion stack.
3. Tabulation (Bottom-Up DP)
Intuition
Iteratively build up the number of ways to reach each cell, starting from the top-left, using a 2D DP table.
Code
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[-1 for _ in range(n)] for _ in range(m)]
# Start block
if obstacleGrid[0][0]:
return 0
dp[0][0] = 1
# Fill table
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue # Already set
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
continue
# Ways from up
if i == 0:
up = 0
else:
up = dp[i - 1][j]
# Ways from left
if j == 0:
left = 0
else:
left = dp[i][j - 1]
dp[i][j] = up + left
return dp[m - 1][n - 1]Explanation
- Fills each cell based on whether it’s blocked, or the sum of ways from above and left.
- Handles boundaries and obstacles directly in the loop.
- The value at
dp[m-1][n-1]is the required answer.
Complexity
- Time: O(m*n) – Every cell is filled once.
- Space: O(m*n) – The entire DP grid.
4. Tabulation with Space Optimization
Intuition
At any cell in row i, you need only the current row and previous row. Using two 1D arrays (curr and prev), you can optimize space from O(m*n) to O(n).
Code
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
prev = [-1] * n
# Start blocked?
if obstacleGrid[0][0]:
return 0
for i in range(m):
curr = [-1] * n
for j in range(n):
# Start cell setup
if i == 0 and j == 0:
curr[0] = 1
continue
# If obstacle, ways = 0
if obstacleGrid[i][j] == 1:
curr[j] = 0
continue
# Ways from up
if i == 0:
up = 0
else:
up = prev[j]
# Ways from left
if j == 0:
left = 0
else:
left = curr[j - 1]
curr[j] = up + left
# Move current to prev for next row
prev = curr
return prev[n - 1]Explanation
- Handles the grid row by row with just two arrays.
- Each cell’s number of paths depends on only the previously completed row (
prev) and the current row (curr). - Reduces extra space use, great for large grids.
Complexity
- Time: O(m*n)
- Space: O(1)
Summary Table
| Approach | Time | Space | Notes |
|---|---|---|---|
| Recursion | O(2^(mn)) | O(m*n) | Not practical, illustrates basics |
| Memoization (Top-Down DP) | O(m*n) | O(m*n) | Efficient, leverages overlapping subproblems |
| Tabulation (Bottom-Up DP) | O(m*n) | O(m*n) | Iterative and intuitive |
| Space-Optimized Tabulation | O(m*n) | O(1) | Best for large grids |
Conclusion
Unique Paths II combines basic grid DP with realistic obstacles, teaching you how to adapt recursion, memoization, and tabulation for path-counting under constraints. Mastering these steps is vital for efficiently solving similar matrix path problems in interviews or real-world scenarios.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
