You are given an m x n integer array obstacleGrid. A robot is initially located at the top-left corner
and tries to reach the bottom-right corner. The robot can only move either down or right.
An obstacle is marked with 1 and empty space with 0.
Return the number of unique paths that do not pass through any obstacle.
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. There are two unique paths: Right→Right→Down→Down and Down→Down→Right→Right.
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
This is an extension of Unique Paths. The key difference is that any cell marked as an obstacle has 0 paths through it.
We modify the DP table to set dp[i][j] = 0 whenever obstacleGrid[i][j] == 1.
- If the start or end cell is an obstacle, immediately return 0.
- Initialize first row and first column: set to 1 only until an obstacle is encountered; all subsequent cells in that row/column become 0.
- For all other cells: if the cell is an obstacle set 0, otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1].
public class UniquePathsII {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 1; i < m; i++)
dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i - 1][0];
for (int j = 1; j < n; j++)
dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j - 1];
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 Analysis:
Time complexity: O(m * n) to traverse every cell once.
Space complexity: O(m * n) for the DP table; can be reduced to O(n) with a 1D array.