Naive Pseudo-code

text
function countPaths(r, c):
    if r or c is out of bounds or grid[r][c] is obstacle:
        return 0
    if r is destination_row and c is destination_col:
        return 1
    return countPaths(r + 1, c) + countPaths(r, c + 1)

Complexity Analysis

The time complexity of this approach is exponential, specifically $O(2^{m+n})$. This occurs because the recursion tree re-calculates the number of paths for the same cells repeatedly. For a grid of size $100 \times 100$, the number of operations far exceeds the limits of modern processors, resulting in a Time Limit Exceeded (TLE) error.

Core Insight for Unique Paths II

The transition from the brute force approach to the optimal solution relies on the observation that the robot can only reach cell $(i, j)$ from two specific directions:

1. From the cell directly above: $(i-1, j)$
2. From the cell directly to the left: $(i, j-1)$

Therefore, the total number of unique paths to reach $(i, j)$ is strictly the sum of the unique paths to reach $(i-1, j)$ and the unique paths to reach $(i, j-1)$.

The obstacle constraint introduces a simple condition: if a cell contains an obstacle, no path can flow through it. Mathematically, this means the number of paths to an obstacle cell is 0. This "zeroing out" effect propagates to subsequent cells; if a path is blocked, it contributes nothing to the sum of its downstream neighbors.

Visual Description: Imagine a 2D table mirroring the grid dimensions. We process this table row by row. For any given cell, we look at the value in the cell above it and the value in the cell to the left of it in our table. We sum these two values to determine the current cell's value. If the current cell corresponds to an obstacle in the input grid, we force the value to 0, effectively cutting off the flow of paths through that coordinate.

Algorithm Strategy: DP - 2D Array (Unique Paths on Grid)

1. State Definition: Let dp[i][j] represent the number of unique paths from the start $(0,0)$ to the cell $(i, j)$.
2. Initialization:
   • Create a 2D array dp of size $m \times n$.
   • Check the starting cell $(0,0)$. If obstacleGrid[0][0] is 1, return 0 immediately (no paths possible). Otherwise, set dp[0][0] = 1.
3. Base Cases (Boundaries):
   • For the first column ($j=0$): A cell is reachable only if the cell above it is reachable and not an obstacle.
   • For the first row ($i=0$): A cell is reachable only if the cell to its left is reachable and not an obstacle.
4. Transition Relation:
   • Iterate through the grid starting from $(1,1)$.
   • If obstacleGrid[i][j] == 1, set dp[i][j] = 0.
   • Otherwise, set dp[i][j] = dp[i-1][j] + dp[i][j-1].
5. Result: The value at dp[m-1][n-1] contains the total unique paths to the destination.

Execution Flow

1. Input Validation: We receive obstacleGrid. Let $m$ be rows and $n$ be columns.
2. Start Check: If obstacleGrid[0][0] is 1, the robot cannot start. Return 0.
3. DP Table Setup: Initialize a table dp[m][n] with zeros. Set dp[0][0] = 1.
4. First Column Processing: Iterate $i$ from 1 to $m-1$. If obstacleGrid[i][0] is 0, dp[i][0] = dp[i-1][0]. If it is 1, dp[i][0] remains 0 (and all subsequent cells in this column remain 0).
5. First Row Processing: Iterate $j$ from 1 to $n-1$. If obstacleGrid[0][j] is 0, dp[0][j] = dp[0][j-1]. If it is 1, dp[0][j] remains 0.
6. Inner Grid Processing:
   • Loop $i$ from 1 to $m-1$.
   • Loop $j$ from 1 to $n-1$.
7. Output: Return dp[m-1][n-1].

Proof of Correctness

The correctness is proven via induction.

• Base Case: The starting position $(0,0)$ has 1 path (standing still), unless blocked. This is correctly initialized.
• Inductive Step: Assume for any cell $(r, c)$, dp[r-1][c] correctly stores paths to the top neighbor and dp[r][c-1] correctly stores paths to the left neighbor. Since the robot can only arrive at $(r, c)$ from these two positions, the sum of paths to these neighbors represents the exhaustive set of paths to $(r, c)$. The obstacle check ensures invalid paths are excluded (adding 0).
• Conclusion: By induction, the value at the bottom-right corner accumulates all valid unique paths.

Reference Implementation

C++ Solution for LeetCode 63

cpp
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        // If the starting cell is an obstacle, no paths exist.
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // DP table initialization
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // Base case
        dp[0][0] = 1;

        // Fill the first column
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = dp[i-1][0];
            } else {
                dp[i][0] = 0;
            }
        }

        // Fill the first row
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0) {
                dp[0][j] = dp[0][j-1];
            } else {
                dp[0][j] = 0;
            }
        }

        // Fill the rest of the grid
        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];
    }
};

Java Solution for LeetCode 63

java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // If start is blocked, return 0
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        // Initialize first column
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = dp[i - 1][0];
            } else {
                dp[i][0] = 0;
            }
        }

        // Initialize first row
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0) {
                dp[0][j] = dp[0][j - 1];
            } else {
                dp[0][j] = 0;
            }
        }

        // Fill DP table
        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];
    }
}

Python Solution for LeetCode 63

python
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        # If starting cell is an obstacle, return 0
        if obstacleGrid[0][0] == 1:
            return 0

        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1

        # Initialize first column
        for i in range(1, m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = 0

        # Initialize first row
        for j in range(1, n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j-1]
            else:
                dp[0][j] = 0

        # Fill DP table
        for i in range(1, m):
            for j in range(1, n):
                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]