How do you solve Unique Paths II?

Use a 2D DP array of the same size as obstacleGrid. Initialize dp[0][0] to 1 if not blocked. For each cell, if it is not an obstacle, set dp[r][c] to the sum of dp[r-1][c] and dp[r][c-1] if those indices are valid. If the cell is an obstacle, set dp[r][c] to 0. The answer is dp[rows-1][cols-1]. This approach runs in O(rows*cols) time and space.

Unique Paths II

Q: What is the time complexity of Unique Paths II?

O(rows * cols). Each cell in the grid is visited exactly once in a nested loop, and each update is O(1), resulting in O(rows * cols) total time.

Q: What pattern does Unique Paths II use?

The Pattern: Dynamic Programming (Grid Path Counting with Obstacles) The Heuristic: When counting paths in a grid with obstacles, use a DP table where each cell accumulates the sum of paths from its top and left neighbors unless blocked, effectively pruning invalid paths early and building the solution bottom-up.

Medium Dynamic Programming

Problem

Given a 2D grid obstacleGrid where some cells are obstacles (marked as 1) and others are free (marked as 0), return the number of unique paths from the top-left corner to the bottom-right corner moving only down or right and avoiding obstacles.

1 ≤ obstacleGrid.length, obstacleGrid[0].length ≤ 100
obstacleGrid[i][j] is 0 or 1

Example

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

Output: 2

The grid has an obstacle at position (1,1). The two unique paths are: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) and (0,0) → (1,0) → (2,0) → (2,1) → (2,2). The algorithm initializes a DP table to count paths, sets the start cell to 1 if not blocked, and iteratively sums paths from the top and left neighbors while skipping obstacles. The critical moment is when the algorithm encounters the obstacle at (1,1) and sets its path count to 0, effectively blocking paths through it.

Approach

Straightforward Solution

A brute-force approach would attempt to enumerate all possible paths recursively, which is exponential in time and infeasible for large grids.

Core Observation

The number of unique paths to any cell is the sum of unique paths to the cell above it and to the left of it, except when the cell is blocked by an obstacle, in which case the number of paths is zero.

Path to Optimal

Preview

Recognizing the problem as a grid-based path counting with obstacles suggests dynamic programming…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a 2D DP array of the same size as obstacleGrid. Initialize dp[0][0] to 1 if not blocked…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(rows * cols)

Each cell in the grid is visited exactly once in a nested loop, and each update is O(1), resulting in O(rows * cols) total time.

Space

O(rows * cols)

A DP table of the same size as the input grid is used to store path counts, requiring O(rows * cols) auxiliary space. This space is necessary to store intermediate results for the bottom-up computation.

Pattern Spotlight

Dynamic Programming (Grid Path Counting with Obstacles)

When counting paths in a grid with obstacles, use a DP table where each cell accumulates the sum of paths from its top and left neighbors unless blocked, effectively pruning invalid paths early and building the solution bottom-up.

Solution

Python

1class Solution:
2    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
3        rows = len(obstacleGrid)
4        cols = len(obstacleGrid[0])
5
6        dp = [[0] * cols for _ in range(rows)]
7
8        if obstacleGrid[0][0] == 1:
9            return 0
10
11        dp[0][0] = 1
12
13        for r in range(rows):
14            for c in range(cols):
15
16                if obstacleGrid[r][c] == 1:
17                    dp[r][c] = 0
18                    continue
19
20                if r > 0:
21                    dp[r][c] += dp[r - 1][c]
22
23                if c > 0:
24                    dp[r][c] += dp[r][c - 1]
25
26        return dp[rows - 1][cols - 1]

Step-by-Step Solution

Initialize DP Table and Handle Starting Cell Obstacle

3rows = len(obstacleGrid)
4cols = len(obstacleGrid[0])
6dp = [[0] * cols for _ in range(rows)]
8if obstacleGrid[0][0] == 1:
9    return 0
11dp[0][0] = 1

Objective

To create a DP table matching the grid size and set the starting point's path count considering obstacles.

Key Insight

Initializing the DP table with zeros sets a clean slate. The starting cell is special: if it is blocked, no paths exist, so return zero immediately. Otherwise, set dp[0][0] to 1 to represent one unique path starting there. This initialization anchors the DP recurrence and prevents invalid path counts from propagating.

Interview Quick-Check

Core Logic

Setting dp[0][0] to 1 if not blocked establishes the base case for the DP recurrence.

State & Boundaries

Early return if the start cell is blocked avoids unnecessary computation and handles edge cases.

Common Pitfalls & Bugs

Failing to check the start cell for an obstacle can lead to incorrect path counts or runtime errors.

Iteratively Accumulate Path Counts While Skipping Obstacles

To fill the DP table by summing paths from the top and left neighbors for each cell, skipping cells blocked by obstacles.

Return the Total Number of Unique Paths to the Destination

To output the computed number of unique paths to the bottom-right corner of the grid.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 26 Critical

return dp[rows - 1][cols - 1]

Return the total number of unique paths to the bottom-right cell.

The DP table's last cell contains the count of all valid unique paths from start to finish, accounting for obstacles.

Line 8 Critical

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

Check if the starting cell is blocked by an obstacle.

If the start cell is blocked, no paths exist, so the algorithm can terminate early, saving computation.

Line 9 Critical

return 0

Return zero immediately if the start cell is blocked.

This early return prevents invalid DP initialization and ensures correctness for edge cases.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why must the DP value for a cell be set to zero if that cell contains an obstacle?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Unique Paths II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Unique Paths II drill

or drill a free problem

1	`class Solution:`
2	`def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:`
3	`rows = len(obstacleGrid)`
4	`cols = len(obstacleGrid[0])`
5
6	`dp = [[0] * cols for _ in range(rows)]`
7
8	`if obstacleGrid[0][0] == 1:`
9	`return 0`
10
11	`dp[0][0] = 1`
12
13	`for r in range(rows):`
14	`for c in range(cols):`
15
16	`if obstacleGrid[r][c] == 1:`
17	`dp[r][c] = 0`
18	`continue`
19
20	`if r > 0:`
21	`dp[r][c] += dp[r - 1][c]`
22
23	`if c > 0:`
24	`dp[r][c] += dp[r][c - 1]`
25
26	`return dp[rows - 1][cols - 1]`

3	`rows = len(obstacleGrid)`
4	`cols = len(obstacleGrid[0])`
6	`dp = [[0] * cols for _ in range(rows)]`
8	`if obstacleGrid[0][0] == 1:`
9	`return 0`
11	`dp[0][0] = 1`