Coin Change

mediumTests passed 2026-11-11v1.0.0
TC: O(A * C)|SC: O(A)
1D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Bottom-up unbounded knapsack minimizing `dp[a]` (min coins for amount `a`). Initialize `dp = [amount + 1] * (amount + 1)` with `dp[0] = 0`, iterate `c` then `a >= c`: `dp[a] = min(dp[a], 1 + dp[a - c])`.

2. Complexity Bounds & Proof

Evaluates C coins against each sub-amount up to A in a 1D array of length `A + 1`.

3. Minimal Idiomatic Code

def coinChange(coins: list[int], amount: int) -> int:
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for a in range(c, amount + 1):
            if dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] <= amount else -1

4. Failure Modes & Interview Follow-ups

Pitfalls:- Greedy largest-coin-first fails canonical non-US denominations like `coins=[1,3,4], amount=6` (`3+3=2` beats `4+1+1=3`). - Returning `amount + 1` sentinel instead of `-1` when unreachable.
Follow-ups:- Minimum BFS path in state graph `[0..amount]` can beat DP when `amount` is huge and largest coin allows early exit.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

Coin Change II (O(A * C))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.