Lab 02 — 2D DP (Unique Paths with Obstacles)

Goal

Solve Unique Paths II (LC 63) with the full brute → memo → tabulated → space-optimized progression. Internalize the canonical 2D DP loop structure (for i: for j:) and the rolling-row trick that reduces O(N · M) space to O(M). After this lab you should be able to write any grid-DP problem from a blank screen in <8 minutes and apply the rolling-row collapse on demand.

Background Concepts

A 2D DP has state dp[i][j] indexed by two integers. For grid problems, (i, j) is a cell, and the recurrence aggregates over the (at most) two predecessors (i-1, j) and (i, j-1). Because each row depends only on the previous row, the table can be rolled down to a single 1D array of length M+1 — half the memory, identical answers.

The grid-DP family is the cleanest 2D DP family because the dependency graph is trivially layered (row by row). It is the right place to learn the rolling-row mechanic before applying it to harder 2D DPs (knapsack, edit distance, LCS).

Interview Context

Unique Paths II is a top-50 Medium DP problem at Microsoft, Amazon, and Bloomberg. The non-obstacle variant (LC 62) shows up at every L3 phone screen. The obstacle variant adds a wrinkle: cells with grid[i][j] == 1 are blocked and contribute 0. Candidates who try a closed-form combinatorial answer (C(N+M-2, N-1)) get stuck the moment obstacles appear — the only general approach is DP. Showing all four stages (brute, memo, tabulated, O(M)-space) signals senior fluency.

Problem Statement

Given an m × n grid obstacleGrid where each cell is either 0 (open) or 1 (obstacle), count the number of distinct paths from (0, 0) to (m-1, n-1). Movement is restricted to right or down by one cell. If the start or end is blocked, the answer is 0.

Constraints

  • 1 ≤ m, n ≤ 100
  • obstacleGrid[i][j] is 0 or 1.
  • The result is guaranteed to fit in a 32-bit signed integer.

Clarifying Questions

  1. Can the start or end be an obstacle? (Yes — answer is 0 if so.)
  2. Are diagonal moves allowed? (No — only right and down.)
  3. Are paths considered distinct if they share intermediate cells? (Yes — only the sequence of moves matters.)
  4. Modular arithmetic required? (No — fits in int32.)
  5. Is m=1, n=1 valid? (Yes; answer is 1 if open, 0 if blocked.)

Examples

[[0,0,0],
 [0,1,0],
 [0,0,0]]                   → 2

[[0,1],
 [0,0]]                     → 1

[[1]]                       → 0   (start blocked)

[[0]]                       → 1

Initial Brute Force

At each open cell, try moving right or down recursively:

def paths_brute(grid):
    m, n = len(grid), len(grid[0])
    def f(i, j):
        if i >= m or j >= n or grid[i][j] == 1:
            return 0
        if i == m - 1 and j == n - 1:
            return 1
        return f(i + 1, j) + f(i, j + 1)
    return f(0, 0)

Brute Force Complexity

Each call branches into two; depth is m + n - 2. Worst-case calls: 2^(m+n-2). At m=n=100, that’s 2^198 ≈ 4 × 10^59 — TLE. Space is O(m+n) for the recursion stack.

Optimization Path

The brute force recomputes f(i, j) exponentially. There are only m × n distinct (i, j) pairs, so memoization collapses time to O(m · n). Tabulation replaces recursion with a row-major loop. Since dp[i][j] reads dp[i-1][j] and dp[i][j-1], the previous row plus the in-progress row are sufficient — collapse to a single 1D array iterated left-to-right (no same-row dependency conflict because we read dp[j-1] before overwriting it, and dp[j] from the previous row is what’s already there).

Final Expected Approach

Define dp[i][j] = number of paths from (0, 0) to (i, j). Recurrence:

dp[0][0] = 1 if grid[0][0] == 0 else 0
dp[i][j] = 0                                if grid[i][j] == 1
         = dp[i-1][j] + dp[i][j-1]          otherwise (treat out-of-bounds as 0)

Roll to 1D: dp[j] += dp[j-1] for each row, with dp[j] = 0 if blocked.

Data Structures Used

  • 2D array dp of size m × n (tabulated).
  • 1D array dp of size n (rolled).
  • For brute / memo: recursion stack + lru_cache.

Correctness Argument

Every path to (i, j) arrives via the cell above or the cell to the left. The number of paths to (i, j) is the sum of paths to those two predecessors (when neither is out-of-bounds and both are open). This holds because the two predecessor paths are disjoint (the last move differs) and exhaust all paths. Blocked cells contribute 0 directly. Base: dp[0][0] = 1 if open, else 0. Induction over the row-major topological order proves correctness for all cells.

Complexity

StageTimeSpace
Brute forceO(2^(m+n))O(m+n)
MemoizedO(m · n)O(m · n)
TabulatedO(m · n)O(m · n)
Space-optimizedO(m · n)O(n)

Implementation Requirements

All four stages.

# ---- Stage 1: Brute force ----
def paths_brute(grid):
    m, n = len(grid), len(grid[0])
    def f(i, j):
        if i >= m or j >= n or grid[i][j] == 1:
            return 0
        if i == m - 1 and j == n - 1:
            return 1
        return f(i + 1, j) + f(i, j + 1)
    return f(0, 0)

# ---- Stage 2: Memoized ----
from functools import lru_cache
def paths_memo(grid):
    m, n = len(grid), len(grid[0])
    @lru_cache(None)
    def f(i, j):
        if i >= m or j >= n or grid[i][j] == 1: return 0
        if i == m - 1 and j == n - 1: return 1
        return f(i + 1, j) + f(i, j + 1)
    return f(0, 0)

# ---- Stage 3: Tabulated ----
def paths_tab(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[m-1][n-1] == 1: return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[i][j] = 0
                continue
            if i > 0: dp[i][j] += dp[i-1][j]
            if j > 0: dp[i][j] += dp[i][j-1]
    return dp[m-1][n-1]

# ---- Stage 4: Space-optimized (1D rolled) ----
def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1: return 0
    dp = [0] * n
    dp[0] = 1
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j-1]
    return dp[n-1]

Tests

  • [[0,0,0],[0,1,0],[0,0,0]] → 2.
  • [[0,1],[0,0]] → 1.
  • [[1]] → 0.
  • [[0]] → 1.
  • [[0,0],[1,1],[0,0]] → 0 (no path past the blocking row).
  • [[0,0,0,0,0]] → 1.
  • [[0],[0],[0]] → 1.
  • m=n=100 with random 10% obstacles — performance test.

Follow-up Questions

  1. “What if there are diagonal moves?” → dp[i][j] += dp[i-1][j-1] as a third predecessor.
  2. “Each cell has a cost; minimize total path cost.” → Min-path-sum (LC 64); min instead of +.
  3. “K obstacles can be removed.” → 3D DP dp[i][j][k] = paths to (i, j) having removed k obstacles.
  4. “Reconstruct one valid path.” → Backtrack through dp from the target; at each cell pick a predecessor with non-zero contribution.
  5. “Grid is enormous (m=n=10^9) but obstacles are sparse.” → Combinatorial answer (C(m+n-2, n-1)) minus inclusion-exclusion over obstacles. Out of scope here.

Product Extension

Routing on a city grid with road closures, robot path planning with obstacles, dependency-graph traversal with disabled edges. The grid-DP framework generalizes to any DAG where the topological order is row-major.

Language/Runtime Follow-ups

  • Python: [[0]*n for _ in range(m)] allocates correctly; [[0]*n]*m shares row references — a classic bug. Use a comprehension.
  • Java: int[][] dp = new int[m][n]; zero-initializes by default.
  • Go: pre-allocate the slice-of-slices explicitly.
  • C++: vector<vector<int>> dp(m, vector<int>(n, 0));.
  • JS/TS: Array.from({length: m}, () => new Array(n).fill(0)) to avoid the shared-reference trap.

Common Bugs

  1. Shared row references in Python: dp = [[0]*n]*m makes all rows alias the same list. Use a comprehension.
  2. Forgetting to check grid[0][0] == 1: if the start is blocked, the answer is 0, but dp[0][0] = 1 would propagate non-zero counts through the grid.
  3. Using if i > 0 and j > 0 instead of two separate ifs — silently misses one of the two predecessors.
  4. Iterating columns outer, rows inner — works for this problem since dp[i][j] only reads upward and leftward, but breaks the rolled-1D version.
  5. Rolled 1D version: forgetting to set dp[j] = 0 on obstacle — old non-zero value persists from the previous row.

Debugging Strategy

Print the full dp table for the 3×3 obstacle example. Expected:

1 1 1
1 0 1
1 1 2

If yours diverges at row 1, suspect the obstacle handling. If at row 2, suspect the dp[j] = 0 reset. For the rolled-1D version, print dp after each row.

Mastery Criteria

  • Recognized this as a 2D grid DP within 60 seconds.
  • Wrote the brute recursion in <2 minutes.
  • Wrote the tabulated 2D version in <5 minutes from blank screen.
  • Performed the rolling-row collapse to 1D in <2 minutes from the tabulated version.
  • Stated O(m·n) time and O(n) space for the final solution unprompted.
  • Articulated why the rolled-1D version iterates left-to-right (no same-row conflict).
  • Solved LC 62 (no obstacles) in <5 minutes.
  • Solved LC 63 unaided in <12 minutes total.
  • Solved LC 64 (min path sum) in <8 minutes by changing + to min.