[Medium] 63. Unique Paths II

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 and 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Examples

Example 1:

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 ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Example 3:

Input: obstacleGrid = [[1,0]]
Output: 0
Explanation: The starting cell is blocked, so no path exists.

Constraints

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1

Thinking Process

An obstacle and space are marked as 1 and 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Define state: what subproblem does dp[i] (or dp[i][j]) represent?
Recurrence: how does the answer build from smaller indices?
Base cases first; optimize space if only prior row/layer is needed.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
1D DP (this problem)	O(n)	O(n) or O(1)	Linear recurrence
2D DP	O(nm)	O(nm) or O(n)	Grid or two-sequence problems
State machine DP	O(n)	O(1)	Buy/sell, hold/not-hold states
Memoization (top-down)	Same as DP	O(n)	Recursive + cache

Solution

Solution 1: Space-Optimized DP (O(n) space)

class Solution {
public:
    /*
        f(i, j) = 0 if obstacleGrid[i][j] == 1
        f(i, j) = f(i-1, j) + f(i, j-1), if obstacleGrid[i][j] == 0
    */
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        const int N = obstacleGrid.size(), M = obstacleGrid[0].size();
        vector<int> dp(M, 0);
        dp[0] = (obstacleGrid[0][0] == 0) ? 1 : 0;
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                }
                else if(j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp.back();
    }
};

Solution Explanation

Approach: 1D DP (this problem)

Key idea: You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

How the code works:

Define state: what subproblem does dp[i] (or dp[i][j]) represent?
Recurrence: how does the answer build from smaller indices?
Base cases first; optimize space if only prior row/layer is needed.

Walkthrough — input obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]], expected output 2:

There is one obstacle in the middle of the 3x3 grid. There are two ways to reach the bottom-right corner:

Right -> Right -> Down -> Down
Down -> Down -> Right -> Right

Algorithm Explanation:

Initialize (Lines 8-9):
- Get dimensions N (rows) and M (columns)
- Initialize dp array of size M (columns) with zeros
- Set dp[0] = 1 if starting cell has no obstacle, else 0
Process Each Row (Lines 11-19):
- For each row i from 0 to N-1:
  - For each column j from 0 to M-1:
    - If obstacle (Line 13): Set dp[j] = 0 (no paths through obstacle)
    - Else if not first column (Line 15): dp[j] += dp[j-1]
      - This accumulates paths from left (dp[j-1]) with paths from top (already in dp[j])
Return (Line 20): dp.back() = dp[M-1] (number of paths to bottom-right)

Why This Works:

Space Optimization: Using 1D array dp[j] stores paths to current row
- Before update: dp[j] = paths from top (previous row)
- After dp[j] += dp[j-1]: dp[j] = paths from top + paths from left
Obstacle Handling: When obstacle encountered, set dp[j] = 0, blocking all paths through that cell
Base Case: dp[0] initialized based on starting cell
Row-by-Row Processing: Each row processes left-to-right, accumulating paths correctly

Example Walkthrough:

For obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]:

Initial: dp = [1, 0, 0]  (starting at (0,0))

Row 0 (i=0):
  j=0: obstacleGrid[0][0]=0, dp[0] stays 1
  j=1: obstacleGrid[0][1]=0, dp[1] += dp[0] → dp[1] = 1
  j=2: obstacleGrid[0][2]=0, dp[2] += dp[1] → dp[2] = 1
  dp = [1, 1, 1]

Row 1 (i=1):
  j=0: obstacleGrid[1][0]=0, dp[0] stays 1 (from top)
  j=1: obstacleGrid[1][1]=1, dp[1] = 0 (obstacle!)
  j=2: obstacleGrid[1][2]=0, dp[2] += dp[1] → dp[2] = 1 + 0 = 1
  dp = [1, 0, 1]

Row 2 (i=2):
  j=0: obstacleGrid[2][0]=0, dp[0] stays 1
  j=1: obstacleGrid[2][1]=0, dp[1] += dp[0] → dp[1] = 0 + 1 = 1
  j=2: obstacleGrid[2][2]=0, dp[2] += dp[1] → dp[2] = 1 + 1 = 2
  dp = [1, 1, 2]

Result: 2 paths

Solution 2: 2D DP (O(m×n) space)

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // Base case: starting cell
        if (obstacleGrid[0][0] == 0) {
            dp[0][0] = 1;
        }
        
        // Fill first row
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0) {
                dp[0][j] = dp[0][j-1];
            }
        }
        
        // Fill first column
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = dp[i-1][0];
            }
        }
        
        // Fill remaining cells
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        return dp[m-1][n-1];
    }
};

Complexity Analysis:

Solution 1 (Space-Optimized):

Time Complexity: O(m × n) - Visit each cell once
Space Complexity: O(n) - Single array of size n (number of columns)

Solution 2 (2D DP):

Time Complexity: O(m × n) - Visit each cell once
Space Complexity: O(m × n) - Full DP table

Key Differences from LC 62:

Obstacle Handling: Check if cell is obstacle before calculating paths
Base Case: Starting cell might be blocked (return 0)
Edge Cases: First row/column can have obstacles blocking subsequent cells

Edge Cases:

Starting cell blocked: obstacleGrid[0][0] == 1 → return 0
Ending cell blocked: obstacleGrid[m-1][n-1] == 1 → return 0
Single cell: m == 1 && n == 1 → return 1 if no obstacle, else 0
Entire row/column blocked: Some paths become impossible

Common Mistakes:

Forgetting to check starting cell: Must initialize dp[0] based on obstacleGrid[0][0]
Not resetting obstacle cells: When obstacle found, must set dp[j] = 0 explicitly
Incorrect space optimization: In 1D version, must handle first column separately (no j > 0 check for dp[0])

LC 62: Unique Paths - Same problem without obstacles
LC 64: Minimum Path Sum - Find minimum cost path
LC 980: Unique Paths III - Must visit all empty cells exactly once
Common Mistakes
Skipping edge cases (empty input, single element, boundaries).
Off-by-one errors in loops and index ranges.
Forgetting to handle the case when no valid answer exists.

Key Takeaways

Define state: what subproblem does dp[i] (or dp[i][j]) represent?
Recurrence: how does the answer build from smaller indices?
Base cases first; optimize space if only prior row/layer is needed.

References

LC 63: Unique Paths II on LeetCode
LeetCode Discuss — LC 63: Unique Paths II
LeetCode Editorial (may require premium)

Template Reference

Array & Matrix

Robina Li

[Medium] 63. Unique Paths II

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution 1: Space-Optimized DP (O(n) space)

Solution Explanation

Algorithm Explanation:

Why This Works:

Example Walkthrough:

Solution 2: 2D DP (O(m×n) space)

Complexity Analysis:

Key Differences from LC 62:

Edge Cases:

Common Mistakes:

Common Mistakes

Key Takeaways

References

Template Reference

Related Posts

Recent Posts

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution 1: Space-Optimized DP (O(n) space)

Solution Explanation

Algorithm Explanation:

Why This Works:

Example Walkthrough:

Solution 2: 2D DP (O(m×n) space)

Complexity Analysis:

Key Differences from LC 62:

Edge Cases:

Common Mistakes:

Related Problems:

Common Mistakes

Key Takeaways

References

Template Reference

Related Posts

Recent Posts