A robot on an m x n grid starts at top-left and must reach bottom-right. Some cells have obstacles. Count unique paths.
Input: [[0,0,0],[0,1,0],[0,0,0]] → Output: 2Input: [[0,1],[0,0]] → Output: 1
DP: dp[i][j] = number of paths to reach (i,j). If obstacle, dp[i][j]=0. Otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1].
- If start or end is obstacle, return 0.
- dp[0][0]=1. First row and column: dp=1 unless obstacle or previous cell was 0.
- Fill dp table: dp[i][j]=0 if obstacle, else sum of above and left.
class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
if (grid[0][0] == 1 || grid[m-1][n-1] == 1) return 0;
grid[0][0] = 1;
for (int i = 1; i < m; i++) grid[i][0] = grid[i][0] == 1 ? 0 : grid[i-1][0];
for (int j = 1; j < n; j++) grid[0][j] = grid[0][j] == 1 ? 0 : grid[0][j-1];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
grid[i][j] = grid[i][j] == 1 ? 0 : grid[i-1][j] + grid[i][j-1];
return grid[m-1][n-1];
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(1)