Unique Paths II

How it works

We can avoid using any extra space by reusing the input grid itself to store the path counts. The key insight is that once we process a cell, we no longer need its original value (which was just 0 or 1 for obstacle). We transform grid so each cell holds the number of paths from that cell to the destination. Obstacles get converted to 0 since no path passes through them.

Steps

1. If the start or destination has an obstacle, return 0.
2. Set grid[M-1][N-1] = 1 to mark the destination.
3. Iterate from the bottom-right to the top-left (skipping the destination cell):
   • If the cell is an obstacle, set it to 0.
   • Otherwise, compute down + right where down is the cell below and right is the cell to the right.
4. Return grid[0][0] as the answer.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(1) extra space.

Where m is the number of rows and n is the number of columns.

Things to watch for

Not Checking Start or End for Obstacles

If either the starting cell grid[0][0] or the destination cell grid[M-1][N-1] contains an obstacle, there are zero paths. Forgetting this check leads to incorrect results.

Incorrect Base Case Initialization

When filling the first row or first column, all cells after an obstacle should have zero paths. A common mistake is initializing the entire edge with 1s without considering that obstacles block all subsequent cells.

Confusing Obstacle Value with Path Count

In the in-place approach, obstacles are marked as 1 in the input but need to become 0 in the DP array. Confusing these values causes obstacles to be counted as having one path.

Off-by-One Errors in Grid Iteration

When iterating bottom-up or right-to-left, ensure loop bounds are correct. Starting at M-1 and going to 0 requires range(M-1, -1, -1) in Python, not range(M-1, 0, -1) which skips the first row.

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        if grid[0][0] == 1 or grid[M - 1][N - 1] == 1:
            return 0

        grid[M - 1][N - 1] = 1

        for r in range(M - 1, -1, -1):
            for c in range(N - 1, -1, -1):
                if r == M - 1 and c == N - 1:
                    continue

                if grid[r][c] == 1:
                    grid[r][c] = 0
                else:
                    down = grid[r + 1][c] if r + 1 < M else 0
                    right = grid[r][c + 1] if c + 1 < N else 0
                    grid[r][c] = down + right

        return grid[0][0]

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int M = grid.size(), N = grid[0].size();
        if (grid[0][0] == 1 || grid[M - 1][N - 1] == 1) {
            return 0;
        }

        grid[M - 1][N - 1] = 1;

        for (int r = M - 1; r >= 0; r--) {
            for (int c = N - 1; c >= 0; c--) {
                if (r == M - 1 && c == N - 1) {
                    continue;
                }

                if (grid[r][c] == 1) {
                    grid[r][c] = 0;
                } else {
                    uint down = (r + 1 < M) ? grid[r + 1][c] : 0;
                    uint right = (c + 1 < N) ? grid[r][c + 1] : 0;
                    grid[r][c] = down + right;
                }
            }
        }

        return grid[0][0];
    }
};