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.

Unique Paths II - LeetCode Solution & Explanation

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.

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

Recognizing the problem as a grid-based path counting with obstacles suggests dynamic programming. The key insight is to build a DP table where each cell stores the count of unique paths to that cell, using the relation dp[r][c] = dp[r-1][c] + dp[r][c-1], but setting dp[r][c] to zero if the cell is an obstacle. Initializing the start cell carefully and iterating row-wise and column-wise ensures all subproblems are solved before use.

Optimal Approach

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.

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.

Solution

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

1

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.

2

Iteratively Accumulate Path Counts While Skipping Obstacles

13for r in range(rows):
  for c in range(cols):
      if obstacleGrid[r][c] == 1:
          dp[r][c] = 0
          continue
      if r > 0:
          dp[r][c] += dp[r - 1][c]
      if c > 0:
          dp[r][c] += dp[r][c - 1]

Objective

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

Key Insight

The DP relation relies on the fact that the number of ways to reach a cell equals the sum of ways to reach the cell above and the cell to the left, provided the current cell is not an obstacle. By iterating row-wise and column-wise, the algorithm ensures that the DP values for neighbors are computed before use. Setting dp[r][c] to zero for obstacles prunes invalid paths, preventing them from contributing to downstream cells.

Interview Quick-Check

Core Logic

The DP recurrence dp[r][c] = dp[r-1][c] + dp[r][c-1] accumulates all valid paths leading to the current cell.

State & Boundaries

Boundary checks (r > 0 and c > 0) prevent index errors and handle the first row and column correctly.

Common Pitfalls & Bugs

Forgetting to skip obstacle cells or incorrectly summing paths can lead to overcounting or runtime errors.

Complexity

The nested loops ensure each cell is processed once, maintaining O(rows * cols) time complexity.

3

Return the Total Number of Unique Paths to the Destination

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

Objective

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

Key Insight

After filling the DP table, the value at dp[rows-1][cols-1] represents the total number of valid unique paths from start to finish, accounting for obstacles. Returning this value completes the bottom-up DP solution.

Interview Quick-Check

Core Logic

The final DP cell contains the total count of unique paths avoiding obstacles.

State & Boundaries

Returning dp[rows-1][cols-1] ensures the answer corresponds to the destination cell.

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.

Line 11 Critical

dp[0][0] = 1

Set the starting cell's path count to one.

This anchors the DP recurrence by indicating there is exactly one way to stand at the start if it is not blocked.

Line 16 Critical

if obstacleGrid[r][c] == 1:

Check if the current cell is an obstacle.

Identifying obstacles is critical to blocking paths through these cells by setting their DP count to zero.

Line 17 Critical

dp[r][c] = 0

Set the DP count for obstacle cells to zero.

This explicitly blocks paths through obstacles, ensuring no invalid paths contribute to downstream cells.

Line 6 Core

dp = [[0] * cols for _ in range(rows)]

Initialize a 2D DP array with zeros matching the grid size.

This DP table stores the count of unique paths to each cell, enabling bottom-up accumulation of path counts.

Line 18 Core

continue

Skip further processing for obstacle cells.

Continuing to the next iteration prevents adding paths from neighbors to blocked cells, maintaining correctness.

Line 20 Core

if r > 0:

If not in the first row, add paths from the cell above.

Paths to the current cell include all paths leading to the cell above, respecting grid boundaries.

Line 21 Core

dp[r][c] += dp[r - 1][c]

Accumulate the number of paths from the cell above.

Adding dp[r-1][c] incorporates all valid paths that reach the current cell from above.

Line 23 Core

if c > 0:

If not in the first column, add paths from the cell to the left.

Paths to the current cell also include all paths leading from the left neighbor, respecting grid boundaries.

Line 24 Core

dp[r][c] += dp[r][c - 1]

Accumulate the number of paths from the cell to the left.

Adding dp[r][c-1] incorporates all valid paths that reach the current cell from the left.

Line 13 Standard

for r in range(rows):

Begin iterating over each row of the grid.

Row-wise iteration ensures that the DP values for cells above are computed before use.

Line 14 Standard

for c in range(cols):

Begin iterating over each column of the current row.

Column-wise iteration ensures that the DP values for cells to the left are computed before use.

Line 3 Basic

rows = len(obstacleGrid)

Calculate the number of rows in the grid.

Caching the number of rows avoids repeated calls to len() and clarifies boundary conditions for iteration.

Line 4 Basic

cols = len(obstacleGrid[0])

Calculate the number of columns in the grid.

Caching the number of columns avoids repeated calls to len() and supports correct indexing in nested loops.

Test Your Understanding

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

Because no path can pass through an obstacle, setting the DP value to zero effectively blocks any paths from continuing through that cell, ensuring the path count only includes valid routes.

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

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`

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]`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize DP Table and Handle Starting Cell Obstacle

Iteratively Accumulate Path Counts While Skipping Obstacles

Return the Total Number of Unique Paths to the Destination

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.