60. Unique Paths II

The number of ways to reach a cell is the sum of the ways to reach the cell above and the cell to the left, since those are the only moves in. Obstacle cells have zero ways. Fill the grid from the top-left; the bottom-right holds the answer.

Idea

A cell (i, j) can only be entered from above (i-1, j) or from the left (i, j-1), so the number of paths into it is the sum of the paths into those two cells. An obstacle cell contributes 0. The start cell has 1 way (do nothing) — unless it's itself an obstacle.

dp[i][j] = 0                              if grid[i][j] is an obstacle
dp[i][j] = dp[i-1][j] + dp[i][j-1]        otherwise

Algorithm

1. If the start is an obstacle, return 0. Set dp[0][0] = 1.
2. Fill row-major: obstacles → 0; otherwise add the cell above and to the left (when in range).
3. Return dp[m-1][n-1].

Worked example: [[0,0,0],[0,1,0],[0,0,0]]

The obstacle at the center blocks the direct diagonal routes, leaving 2 unique paths.

Complexity

• Time: O(m·n).
• Space: O(m·n) (reducible to O(n)).

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i > 0) {
                    dp[i][j] += dp[i - 1][j];
                }
                if (j > 0) {
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}