Chapter 4: Handling Obstacles - Unique Paths II

In the last chapter, we mastered navigating an open grid. But what happens when the path isn't clear? In many real-world scenarios and programming challenges, we must account for constraints and obstacles. LeetCode's "Unique Paths II" (Problem #63) is the perfect extension of our previous problem, forcing us to adapt our grid traversal logic to handle blocked paths.

This chapter is all about handling invalid states within our DP solution, a crucial skill for more advanced problems.

The Problem:

You are given an m x n integer array grid where 0 represents an empty space and 1 represents an obstacle.

A robot is located at the top-left corner (0, 0). The robot can only move either down or right at any point in time and is trying to reach the bottom-right corner (m-1, n-1).

Return the number of possible unique paths. If the start or end cell is an obstacle, no path is possible.

For example:

• grid = [[0,0,0],[0,1,0],[0,0,0]] -> The answer is 2. There is one obstacle in the middle.

• grid = [[0,1],[0,0]] -> The answer is 1.

Approach 1: The Recursive Solution

Our fundamental recursive logic remains the same: the number of paths to cell (row, col) is the sum of paths from the cell above and the cell to the left.

However, we need to add a crucial new condition:

• If the cell (row, col) contains an obstacle (grid[row][col] == 1), then there are 0 paths to it. This becomes our most important base case.

Let's update our implementation.

from typing import List

def uniquePathsWithObstacles_recursive(obstacleGrid: List[List[int]]) -> int:
    m, n = len(obstacleGrid), len(obstacleGrid[0])

    # If the starting cell itself is an obstacle, no paths are possible.
    if obstacleGrid[0][0] == 1:
        return 0

    def solve(row, col):
        # Base case: If the current cell is an obstacle, there are no paths.
        if obstacleGrid[row][col] == 1:
            return 0

        # Base case: If we're at the starting cell (0,0), there is one path.
        if row == 0 and col == 0:
            return 1

        # Recursive step
        from_above = solve(row - 1, col) if row > 0 else 0
        from_left = solve(row, col - 1) if col > 0 else 0

        return from_above + from_left

    return solve(m - 1, n - 1)

# Trying it out
# print(uniquePathsWithObstacles_recursive([[0,0,0],[0,1,0],[0,0,0]])) # Output: 2
# print(uniquePathsWithObstacles_recursive([[0]*15 for _ in range(15)])) # Very slow!

The logic is sound, but just like before, the massive number of overlapping subproblems makes this solution too slow for anything but small grids.

Approach 2: Memoization with a Decorator (Top-Down DP)

The fix is familiar and effective. We can use a cache to store the results of solve(row, col) so that we only compute the paths for each cell once.

import functools
from typing import List

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

        if obstacleGrid[0][0] == 1:
            return 0

        @functools.lru_cache(maxsize=None)
        def solve(row, col):
            if obstacleGrid[row][col] == 1:
                return 0

            if row == 0 and col == 0:
                return 1

            from_above = solve(row - 1, col) if row > 0 else 0
            from_left = solve(row, col - 1) if col > 0 else 0

            return from_above + from_left

        return solve(m - 1, n - 1)

# Trying it out
# solver = Solution()
# print(solver.uniquePathsWithObstacles_memoized([[0]*15 for _ in range(15)])) # Instant!

With memoization, our intuitive recursive solution becomes efficient enough to pass LeetCode's tests. It elegantly handles the obstacle logic without sacrificing the readability of the original recursive structure.

Approach 3: Iteration (Bottom-Up DP)

For the bottom-up approach, we'll once again use a 2D dp table. However, our initialization and iteration logic must now account for obstacles.

1. Create an m x n dp grid, initialized to all zeros.

2. Handle the starting cell: If grid[0][0] is not an obstacle, set dp[0][0] = 1. If it is, no paths are possible, and we can stop.

3. Initialize the first row and column: Iterate through the first column. If a cell (i, 0) is not an obstacle, the paths to it are equal to the paths to the cell above it, dp[i-1][0]. If we hit an obstacle, all subsequent cells in that column will have 0 paths. Do the same for the first row.

4. Iterate through the rest of the grid: For each cell (row, col):

   • If grid[row][col] is an obstacle, dp[row][col] remains 0.

   • Otherwise, dp[row][col] = dp[row - 1][col] + dp[row][col - 1].

The final answer is in dp[m-1][n-1].

def uniquePathsWithObstacles_iterative(obstacleGrid: List[List[int]]) -> int:
    m, n = len(obstacleGrid), len(obstacleGrid[0])

    # If starting or ending point is an obstacle, return 0
    if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
        return 0

    dp = [[0 for _ in range(n)] for _ in range(m)]
    dp[0][0] = 1 # We can reach the start cell

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

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

    # Fill the rest of the grid
    for r in range(1, m):
        for c in range(1, n):
            if obstacleGrid[r][c] == 0:
                dp[r][c] = dp[r-1][c] + dp[r][c-1]

    return dp[m-1][n-1]

# Trying it out
# print(uniquePathsWithObstacles_iterative([[0,0,0],[0,1,0],[0,0,0]])) # 2

This bottom-up approach is very robust. It systematically builds the solution by explicitly checking for obstacles at every step, making it both efficient and easy to follow.

Conclusion

This chapter added a critical layer to our DP skillset: managing constraints. We learned that an obstacle is simply a state in our DP table that evaluates to zero. By incorporating this logic into our base cases and iterative updates, we could solve a more complex problem using the exact same framework we've been practicing.

This idea of handling "zero states" or "invalid states" will be essential as we tackle problems with more complex rules and conditions.