Unique Paths II

Like Unique Paths, but some cells are blocked by obstacles (1 = blocked, 0 = free). Return the number of unique paths from top-left to bottom-right.

Why this is worth learning

An obstacle removes a vertex from the path graph. Its count must become zero immediately so it cannot leak an earlier row’s paths into the current row.

Before coding: one-minute experiment

For [[0,0,0],[0,1,0],[0,0,0]], show the one-dimensional counts after each row.

Function signature

func UniquePathsWithObstacles(obstacleGrid [][]int) int

Inputs / outputs

• obstacleGrid: grid of 0/1 values.
• Return: number of unique paths.

Example

0 0 0
0 1 0
0 0 0
Output: 2

Constraints

• 1 <= m, n <= 100
• The grid is rectangular and contains only 0 (free) and 1 (blocked).
• For every cell, the number of valid paths from the start to that cell is guaranteed to fit the target Go int, including cells from which the destination cannot be reached.

Core idea (near-solution)

DP with obstacles: if a cell is blocked, its path count is 0; otherwise sum from top and left.

Invariant: before updating an interior column c>0, dp[c] still stores the previous row’s path counts from above, while dp[c-1] already stores the current row’s value from the left. After the write, dp[c] has the current cell’s answer.

Algorithm (step-by-step)

1. If start is blocked, return 0.
2. Initialize dp[0] = 1.
3. For each cell (row-major):
   • If obstacle, set dp[c] = 0.
   • Else if c > 0, dp[c] += dp[c-1].
4. Return dp[n-1].

Correctness sketch

The same disjoint last-move recurrence as Unique Paths applies to unblocked cells. A blocked cell has no valid paths ending there, regardless of its predecessor counts, so assign zero. Initialize only the start contribution, then scan left to right: old dp[c] counts arrival from above and new dp[c-1] counts arrival from the left. Resetting an obstacle preserves both the interpretation of the current cell and the next cell’s left predecessor. Induction over row-major order yields the endpoint count; a blocked start or finish consequently has zero paths.

Trace (hand walkthrough)

Example input:
0 0 0
0 1 0
0 0 0
Output: 2

Walk:
- row0: [1,1,1]
- row1 (obstacle at col1): [1,0,1]
- row2: [1,1,2] -> 2 paths

Pitfalls to avoid

• Forgetting to zero dp at obstacles.
• Mishandling the first row/column with obstacles.

Debugging lens

Test blocked start/end, an obstacle in the first row, and a barrier cutting the grid in two. The grid is read-only. Exact counts require every intermediate count—not just the final possibly-zero endpoint—to fit int.

Complexity

• Time: O(m*n).
• Extra space: O(n).

Implementation notes (Go)

• Update dp in-place; it represents the current row.

Contract precision

The grid is not mutated. The representability guarantee covers every prefix-cell count, not only the returned count: a later blocking barrier can make the answer zero after an earlier prefix count becomes enormous. Inputs outside that guarantee are unsupported by this int API.

Reconstruction checkpoint

For [[0,0,0],[0,1,0],[0,0,0]], show the one-dimensional counts after each row.

Return to 2D DP · Module quiz