LeetCode 63: Unique Paths II Solution in Python Explained

Problem Statement

LeetCode 63, Unique Paths II, is a medium-level problem where you’re given an (m \times n) grid represented as a 2D array obstacleGrid. Each cell is either 0 (empty) or 1 (obstacle). Your task is to find the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1,n-1), moving only right or down, avoiding obstacles. Return the total number of possible paths as an integer.

Constraints

1 <= m, n <= 100: Grid dimensions are between 1 and 100.
obstacleGrid[i][j] is 0 or 1: Cells are either empty or obstacles.

Example

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: 3x3 grid with obstacle at (1,1):
Paths: 
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Total = 2

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Explanation: 2x2 grid with obstacle at (0,1):
Only path: Down -> Right

Input: obstacleGrid = [[1]]
Output: 0
Explanation: 1x1 grid with obstacle, no paths possible.

Understanding the Problem

How do you solve LeetCode 63: Unique Paths II in Python? For obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]], count unique paths from (0,0) to (2,2), avoiding the obstacle at (1,1)—here, there are 2 paths. Like LeetCode 62, we move right or down, but obstacles block certain cells. We’ll explore two approaches: a Dynamic Programming Solution (optimal and primary) and an Alternative with Space-Optimized DP (more efficient in space). The DP method runs in O(m * n) time with O(m * n) space, adapting to obstacles.

Solution 1: Dynamic Programming Approach (Primary)

Explanation

Use a 2D DP table where dp[i][j] represents the number of unique paths to reach position (i,j) from (0,0). If a cell has an obstacle, set dp[i][j] = 0. Otherwise, dp[i][j] = dp[i-1][j] + dp[i][j-1] (sum of paths from above and left). Initialize the first row and column based on obstacles, then fill the table.

Here’s a flow for [[0,0,0],[0,1,0],[0,0,0]]:

DP table:
[1,1,1]    [1,1,1]
[1,0,0] -> [1,0,1]
[1,0,0]    [1,1,2]
Result: dp[2][2] = 2

Initialize DP Table.

Create \(m \times n\) table, set first cell based on (0,0).

Fill First Row and Column.

Propagate 1s until an obstacle is hit.

Fill Table.

Sum paths from above and left, 0 if obstacle.

Return Result.

Value at dp[m-1][n-1].

Step-by-Step Example

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

We need 2.

Goal: Count unique paths in 3x3 grid with obstacle.
Result for Reference: 2.
Start: m = 3, n = 3, dp = [[0,0,0],[0,0,0],[0,0,0]].
Step 1: Initialize first cell.

obstacleGrid[0][0] = 0, dp[0][0] = 1.

Step 2: Fill first row.

dp[0][1] = 1 (no obstacle), dp[0][2] = 1, dp[0] = [1,1,1].

Step 3: Fill first column.

dp[1][0] = 1, dp[2][0] = 1, dp = [[1,1,1],[1,0,0],[1,0,0]].

Step 4: Fill table.

dp[1][1]: obstacle = 1, dp[1][1] = 0.
dp[1][2] = dp[1][1] + dp[0][2] = 0 + 1 = 1.
dp[2][1] = dp[2][0] + dp[1][1] = 1 + 0 = 1.
dp[2][2] = dp[2][1] + dp[1][2] = 1 + 1 = 2.
dp = [[1,1,1],[1,0,1],[1,1,2]].

Finish: Return dp[2][2] = 2.

Example 2: obstacleGrid = [[0,1],[0,0]]

We need 1.

Start: dp = [[0,0],[0,0]].
Step 1: dp[0][0] = 1.
Step 2: First row: dp[0][1] = 0 (obstacle).
Step 3: First column: dp[1][0] = 1.
Step 4: dp[1][1] = dp[1][0] + dp[0][1] = 1 + 0 = 1.

dp = [[1,0],[1,1]].

Finish: Return dp[1][1] = 1.

How the Code Works (Dynamic Programming)

Here’s the Python code with line-by-line explanation:

def uniquePathsWithObstacles(obstacleGrid: list[list[int]]) -> int:
    # Line 1: Handle edge case (start is obstacle)
    if obstacleGrid[0][0] == 1:
        return 0

    # Line 2: Initialize DP table
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

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

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

    # Line 5: Fill rest of table
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    # Line 6: Return number of unique paths
    return dp[m-1][n-1]

Alternative: Space-Optimized DP Approach

Explanation

Optimize space by using a 1D DP array, updating it row by row. Each cell dp[j] represents paths to (i,j), and we only need the current row and previous row’s values, reducing space to O(n).

Initialize 1D DP.

Size \(n\), set based on first row.

Process Rows.

Update array for each row, considering obstacles.

Return Result.

Last element of array.

Step-by-Step Example (Alternative)

For [[0,0,0],[0,1,0],[0,0,0]]:

Start: dp = [0,0,0].
Step 1: First row: dp = [1,1,1].
Step 2: Second row.

dp[0] = 1, dp[1] = 0 (obstacle), dp[2] = 1 (1+0).

Step 3: Third row.

dp[0] = 1, dp[1] = 1 (1+0), dp[2] = 2 (1+1).

Finish: Return dp[2] = 2.

How the Code Works (Space-Optimized DP)

def uniquePathsWithObstaclesOpt(obstacleGrid: list[list[int]]) -> int:
    # Line 1: Handle edge case
    if obstacleGrid[0][0] == 1:
        return 0

    # Line 2: Initialize 1D DP array
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0] * n
    dp[0] = 1

    # Line 3: Process each row
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j-1]

    # Line 4: Return number of unique paths
    return dp[n-1]

Complexity

Dynamic Programming:

Time: O(m * n) – Fill \(m \times n\) table.
Space: O(m * n) – Store DP table.

Space-Optimized DP:

Time: O(m * n) – Process each cell.
Space: O(n) – 1D array.

Efficiency Notes

Space-Optimized DP is O(m * n) time and O(n) space, more efficient than the full DP’s O(m * n) space, making it a strong choice for LeetCode 63. Both are O(m * n) time, suitable for the problem size.

Key Insights

Tips to master LeetCode 63:

Obstacle Impact: Set 0 for blocked cells.
DP Flexibility: Adapt LeetCode 62 with obstacles.
Space Saving: Use 1D array for efficiency.

Additional Example

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

Goal: 0.
DP: dp = [[1,1],[0,0]], no path to (1,1).
Result: 0.

Edge Cases

Single Cell: [[0]] – Return 1; [[1]] – Return 0.
All Obstacles: [[1,0]] – Return 0.
No Obstacles: Same as LeetCode 62.

Final Thoughts

The Dynamic Programming solution is a reliable pick for LeetCode 63 in Python—clear and adaptable, with the Space-Optimized version offering a memory boost. For a related challenge, try LeetCode 62: Unique Paths without obstacles! Ready to navigate? Solve LeetCode 63 on LeetCode now and test it with [[0,0,0],[0,1,0],[0,0,0]] or [[0,1],[0,0]] to master pathfinding with obstacles. Dive in and chart the course!