1. Problem Statement (Simple Explanation)
Similar to Unique Paths (62), but now we have obstacles.
You’re given an m x n grid obstacleGrid:
0 = free cell.
1 = obstacle.
Robot:
Starts at top-left: (0, 0).
Wants to reach bottom-right: (m-1, n-1).
Can only move right or down.
Cannot step on cells with obstacles (1).
Return the number of unique paths from start to goal, avoiding obstacles.
Answer is guaranteed ≤ 2 * 109.
2. Examples
Example 1:
Input:
obstacleGrid = [
[0,0,0],
[0,1,0],
[0,0,0]
]
There is one obstacle in the middle (1,1).
Valid paths:
Right → Right → Down → Down
Down → Down → Right → Right
Output: 2
Example 2:
Input:
obstacleGrid = [
[0,1],
[0,0]
]
Only one path is valid due to the obstacle at (0,1):
Down → Right
Output: 1
3. Approach – Dynamic Programming with Obstacles (O(m·n))
We extend the DP approach from Problem 62, but incorporate obstacles.
Let dp[i][j] = number of unique paths to reach cell (i, j).
Rules:
If obstacleGrid[i][j] == 1, then dp[i][j] = 0 (cannot stand there).
Else, if i == 0 and j == 0 (start cell):
dp[0][0] = 1 if not an obstacle.
Else:
dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0)
We can compress to 1D DP:
dp[j] represents the number of ways to reach (current_row, j).
For each row i and column j:
If obstacleGrid[i][j] == 1:
dp[j] = 0 (no paths through an obstacle).
Else:
If j > 0, dp[j] += dp[j-1] (add ways from left).
If j == 0, just keep dp[j] as is (only from above).
Initialization:
dp[0] = 1 if start cell (0,0) is not an obstacle.
If (0,0) is obstacle → dp[0] = 0, answer is 0.
1D DP Pseudo-code:
dp[j] already includes ways from above.
dp[j-1] is ways from the left in current row.
When we see obstacle: we set dp[j] = 0 (no ways to get there).
First cell is set to 1 if no obstacle, else 0.
Complexity:
Let m = number of rows, n = number of columns:
Time: O(m⋅n)
Extra space: O(n)
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment