#63

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Unique Paths II

Calculate the number of unique paths from top-left to bottom-right in a grid with obstacles using dynamic programming state transitions.

array dynamic programming matrix

Problem Statement

You are given an m x n integer matrix representing a grid, where a robot starts at the top-left corner (grid[0][0]). The robot can only move right or down, and some cells contain obstacles marked as 1. Your task is to compute the total number of unique paths that allow the robot to reach the bottom-right corner (grid[m-1][n-1]) without entering any obstacles.

Each cell in the grid is either free (0) or blocked by an obstacle (1). You must design a solution that efficiently counts the number of valid paths while handling edge cases where paths are blocked by obstacles. Return the total number of distinct paths to the bottom-right, considering that no path may cross a blocked cell.

Examples

Example 1

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

Output: 2

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

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

Example 2

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

Output: 1

Example details omitted.

Constraints

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

Solution Approach

Dynamic Programming Table

Create a 2D DP array of the same size as the grid, where each cell dp[i][j] represents the number of unique ways to reach that cell. Initialize dp[0][0] to 1 if it's free, else 0. Then iterate through the grid, updating dp[i][j] as the sum of dp[i-1][j] and dp[i][j-1] for free cells, while setting dp[i][j] to 0 for obstacles. This approach directly applies the state transition DP pattern and ensures correct path counting even with obstacles.

Space Optimization

Since each DP cell depends only on the cell above and to the left, you can reduce space complexity by using a single 1D array representing the current row. Update each element by adding the value from the left and the previous value from the array, skipping updates for obstacle cells. This optimization keeps the solution aligned with the DP state transition logic while lowering memory usage, which is crucial for larger grids.

Edge Case Handling

Carefully handle the first row and first column, as they have only one direction to inherit paths from. If an obstacle appears, set all subsequent cells in that row or column to 0 to avoid invalid paths. Additionally, confirm that the start and end cells are not blocked; if either is an obstacle, immediately return 0. These checks prevent common DP mistakes and ensure the state transition correctly models obstacle constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The DP table approach iterates through every cell once, giving O(m n) time complexity, and uses O(m n) space for the table. With space optimization, the space reduces to O(n) while maintaining O(m*n) time complexity, which is consistent with the solution and accounts for the number of grid cells and state transitions explicitly.

What Interviewers Usually Probe

Do you recognize how obstacles affect the standard unique paths DP formula?
Can you optimize space while maintaining correct path counts through the state transition?
Will you handle edge cases where the start or end cell is blocked?

Common Pitfalls or Variants

Common pitfalls

Forgetting to set paths to 0 in cells that contain obstacles, which can inflate path counts.
Not properly initializing the first row and column, leading to incorrect cumulative sums when obstacles exist.
Assuming all grids have at least one valid path, ignoring cases where the start or end cell is an obstacle.

Follow-up variants

Unique Paths I: No obstacles, simpler DP state transition with guaranteed paths.
Count Paths with Diagonal Moves: Allow right, down, and diagonal movements, adjusting DP transitions.
Minimum Path Sum with Obstacles: Compute the path with the minimal sum of cell values while avoiding obstacles.

FAQ

How do obstacles affect the DP state transition in Unique Paths II?

Obstacles are treated as cells with 0 paths. In the DP transition, any cell that is blocked does not contribute to the cumulative path count, ensuring that no paths go through obstacles.

What is the time and space complexity of this approach?

The DP solution iterates over all m n cells, giving O(m n) time. Using a 2D table is O(m*n) space, but optimized 1D row storage reduces space to O(n).

Can the robot move diagonally in Unique Paths II?

No, the robot can only move right or down. Any DP approach must account only for these directions when summing paths to each cell, respecting obstacle placement.

What should be returned if the start or end cell is an obstacle?

If either the top-left or bottom-right cell is blocked, the robot cannot start or finish, so the function should immediately return 0 without computing the DP table.

How can I optimize memory usage for larger grids?

Use a single 1D array representing the current row and update it in place by summing left and previous row values, skipping obstacle cells to reduce memory while keeping DP logic correct.

terminal

Solution

Solution 1: Memoization Search

We design a function $\textit{dfs}(i, j)$ to represent the number of paths from the grid $(i, j)$ to the grid $(m - 1, n - 1)$. Here, $m$ and $n$ are the number of rows and columns of the grid, respectively.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n or obstacleGrid[i][j]:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            return dfs(i + 1, j) + dfs(i, j + 1)

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        return dfs(0, 0)

Solution 2: Dynamic Programming

We can use a dynamic programming approach by defining a 2D array $f$, where $f[i][j]$ represents the number of paths from the grid $(0,0)$ to the grid $(i,j)$.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n or obstacleGrid[i][j]:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            return dfs(i + 1, j) + dfs(i, j + 1)

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        return dfs(0, 0)

Continue Practicing

#64 minimum path sum #85 maximal rectangle #221 maximal square