How to Solve Unique Paths II

This problem requires counting all valid paths from the top-left to bottom-right corner of a grid while avoiding obstacles. Using state transition dynamic programming, you track the number of ways to reach each cell by summing paths from the top and left, skipping cells with obstacles. This ensures an efficient solution that directly leverages the DP pattern rather than exploring all permutations recursively.

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:

1. Right -> Right -> Down -> Down
2. 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

The DP table approach iterates through every cell once, giving O(mn) time complexity, and uses O(mn) 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.

How GhostInterview Helps

• Capture the grid input including obstacles and highlight blocked cells automatically for clarity.
• Provide the step-by-step DP table updates along with cumulative path counts and time/space complexity explanation.
• Support screen-share workflows by visualizing each DP layer, showing current row updates and obstacle impact in real time.

Topic Pages

• Array
• Dynamic Programming
• Matrix

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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 mn cells, giving O(mn) 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.