Unique Paths

mediumTests passed 2026-11-11v1.0.0
TC: O(M * N)|SC: O(N)
2D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Rolling 1D row of width `n` initialized to `1`: `dp[j] += dp[j - 1]` combines ways from top (`prev dp[j]`) and left (`updated dp[j-1]`). Or closed-form binomial `C(m + n - 2, min(m, n) - 1)`.

2. Complexity Bounds & Proof

Wait: closed-form `C(m+n-2, min(m,n)-1)` runs in O(min(M, N)) time and O(1) space; rolling 1D DP handles obstacles smoothly in follow-ups.

3. Minimal Idiomatic Code

def uniquePaths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[-1]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Overflow on intermediate factorial `(m+n-2)!` if computing closed-form naively instead of multiplicative loop or DP.
Follow-ups:- Unique Paths II adds obstacles (`obstacleGrid[r][c] == 1 -> dp[c] = 0`).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Climbing Stairs (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.