Blind 75 Visualized

#5 · 1D DP

Coin Change

Given coin denominations and a target amount, return the fewest coins needed to make that amount, or −1 if it is impossible. Each coin can be used any number of times.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

1-D DP table

dp[a] stores the answer to the subproblem "fewest coins for amount a". The answer to a bigger amount is built from smaller, already-solved ones: dp[a] = 1 + min(dp[a − coin]).

Memory layout

A single contiguous array of amount + 1 integers. The inner loop reads dp[a − coin] for a handful of coins, which is cache-friendly and branch-predictable, with no hashing or recursion frames.

OperationCost
fill the tableO(amount × coins)
spaceO(amount)
read one cellO(1)

Hash map memo (top-down)

Caches the result of each recursive call keyed by the remaining amount, so each distinct amount is solved once.

Memory layout

Hash buckets of boxed entries: up to `amount` entries, with hashing and pointer overhead, plus a recursion stack up to depth amount / minCoin.

OperationCost
lookup / insertO(1) average
recursion depthO(amount / min(coin))

Why it fits

  • Optimal substructure: if the best way to make a uses coin c, then the rest must be the best way to make a − c. So dp[a] depends only on smaller amounts.
  • Overlapping subproblems: the same remaining amount is reached through many coin orderings (1+3 and 3+1 both leave 2). Caching turns exponential recursion into amount × coins steps.
  • A table is the right shape because the subproblem space is a dense range 0..amount, so a plain array beats a hash map on speed and memory.

Why alternatives degrade

Greedy (largest coin first):
Not correct for arbitrary denominations: with coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 = 3 coins, but 3 + 3 uses only 2.
Plain recursion:
Re-solves the same amounts in every branch, so the call count grows exponentially with amount.
BFS over amounts:
Correct (shortest path in an implicit graph) and also O(amount × coins), but it needs a queue and visited set, which is more memory than a single array.

Four approaches, from naive to production

1 · beginner

Plain recursion over remaining amount

time O(coins^(amount / min coin)): exponentialspace O(amount / min coin) call stack

To make rem, try every coin that fits, solve the smaller problem rem − coin recursively, and keep the best.

int coinChange(vector<int>& coins, int amount) {
    const int INF = 1e9;
    function<int(int)> minCoins = [&](int rem) -> int {
        if (rem == 0) return 0;
        int best = INF;
        for (int coin : coins) {
            if (coin <= rem) best = min(best, 1 + minCoins(rem - coin));
        }
        return best;
    };
    int ans = minCoins(amount);
    return ans >= INF ? -1 : ans;
}

Flaws & bottlenecks

  • Exponential: the same remaining amount is recomputed in many branches (watch the cells being rewritten).
  • Deep recursion: with coin 1 and amount 10⁴, depth reaches 10⁴ and can overflow the stack.
  • Every call does a full loop over coins even when the answer for that amount is already known.

Interviewer cross-questions

Why is this so slow?

Say: Overlapping subproblems. For amount 6 with coins [1,3,4] it makes 24 calls for only 7 distinct amounts, and the gap grows exponentially. The call tree recomputes minCoins(2), for instance, in several branches.

Would a greedy approach work instead?

Say: Only for canonical coin systems (like US coins). With [1,3,4] and amount 6, greedy picks 4+1+1 = 3 coins while 3+3 = 2 is optimal. DP is required for arbitrary denominations.

What is the base case when the amount cannot be formed?

Say: If no coin fits, best stays at Infinity, which propagates upward (1 + Infinity = Infinity). The caller converts a final Infinity to −1.

2 · intermediate

Top-down recursion with memoization

time O(amount × coins)space O(amount) map + O(amount) stack

Same recursion, but cache minCoins(rem) in a map so each remaining amount is solved at most once.

int coinChange(vector<int>& coins, int amount) {
    const int INF = 1e9;
    unordered_map<int, int> memo;
    function<int(int)> minCoins = [&](int rem) -> int {
        if (rem == 0) return 0;
        auto it = memo.find(rem);
        if (it != memo.end()) return it->second;
        int best = INF;
        for (int coin : coins) {
            if (coin <= rem) best = min(best, 1 + minCoins(rem - coin));
        }
        memo[rem] = best;
        return best;
    };
    int ans = minCoins(amount);
    return ans >= INF ? -1 : ans;
}

Flaws & bottlenecks

  • Still recursive: depth up to amount / min(coin) can overflow the stack for big amounts.
  • Hash map overhead (boxing, hashing, rehashing) for what is really a dense integer range.
  • Only the amounts reachable from the target get computed, which is a saving on sparse inputs but gives no cache-locality benefit.

Interviewer cross-questions

What changed to get from exponential to polynomial?

Say: The memo guarantees each of the amount + 1 distinct states is expanded once, and each expansion loops over the coins: O(amount × coins) total. Cache hits return in O(1).

Top-down or bottom-up: which would you use?

Say: Bottom-up in production: no recursion limit and better locality. Top-down is easier to derive and only computes states that are actually reachable, which helps when the state space is huge but sparsely used.

How do you avoid recursion-depth problems?

Say: Convert to the bottom-up table: iterate a from 1 to amount so dependencies are always already computed. Or raise the stack limit / run in a thread with a bigger stack, which is only a band-aid.

3 · advanced

Bottom-up DP table

time O(amount × coins)space O(amount)

Fill dp[0..amount] in increasing order: dp[a] = 1 + min over coins of dp[a − coin].

int coinChange(vector<int>& coins, int amount) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a) dp[a] = min(dp[a], dp[a - coin] + 1);
        }
    }
    return dp[amount] >= INF ? -1 : dp[amount];
}

Flaws & bottlenecks

  • Computes every amount up to the target, including ones the optimal path never needs.
  • Infinity is a float: mixing it into integer arrays forces slower double-typed storage in some engines.
  • O(amount) memory can be large for huge targets (e.g. 10⁹), where this approach is infeasible.

Interviewer cross-questions

Why iterate amounts in increasing order?

Say: dp[a] depends on dp[a − coin] with smaller indices. Filling left to right guarantees those cells are already final when we read them, so no recursion is needed.

Can you reduce the space?

Say: Not below O(amount) in general, since dp[a] may need to look back by any coin value. If the largest coin is C, a rolling window of size C + 1 suffices, which helps when coins are small and the target is huge.

What if the amount is up to 10⁹?

Say: The table is infeasible. With a few small coins the optimal solution uses mostly the largest coin, so reduce the amount by taking max(coin) as many times as possible while keeping a small remainder window, then DP the remainder. For arbitrary coins this becomes an integer-programming problem.

4 · expert

Int32 table, sorted coins, early break

time O(amount × coins)space O(amount), one Int32Array

Same recurrence, hardened and tuned: validate inputs, drop invalid coins, sort them so the inner loop can break early, and use a sentinel amount + 1 in an Int32Array instead of Infinity.

int coinChange(vector<int>& coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0 || coins.empty()) return -1;
    vector<int> sorted;
    for (int c : coins) if (c > 0) sorted.push_back(c);
    sort(sorted.begin(), sorted.end());
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (size_t k = 0; k < sorted.size(); k++) {
            int coin = sorted[k];
            if (coin > a) break;
            int cand = dp[a - coin] + 1;
            if (cand < dp[a]) dp[a] = cand;
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Flaws & bottlenecks

  • The sentinel amount + 1 only works because the answer can never exceed amount coins (needs coins ≥ 1); it overflows nothing, but it is a subtle invariant to document.
  • Sorting costs O(k log k) once, which is negligible, but the early break only helps when coins are spread widely.
  • Still O(amount) memory and O(amount × coins) time; this tuning improves constants, not the asymptotics.

Interviewer cross-questions

Why use amount + 1 instead of Infinity?

Say: An optimal answer never uses more than amount coins (each coin is worth at least 1), so amount + 1 is a safe "unreachable" marker. It keeps the array integer-typed (Int32Array), avoids float arithmetic, and the final check dp[amount] > amount maps cleanly to −1.

What does sorting the coins buy you?

Say: Once coin > a, all larger coins are also too big, so we break instead of testing them. For small a with many large coins this skips most of the inner loop. It also improves branch prediction since the comparison flips only once.

What edge cases do you test?

Say: amount = 0 (answer 0), no coins, a coin larger than the amount, an unreachable amount (coins [2], amount 3 → −1), duplicate coins, a coin of 0 or a negative value (filtered), and a large amount to check performance.

Synchronized code walkthrough

Showing: Plain recursion over remaining amount — shares the player above; click any step to jump.

int coinChange(vector<int>& coins, int amount) {
    const int INF = 1e9;
    function<int(int)> minCoins = [&](int rem) -> int {
        if (rem == 0) return 0;
        int best = INF;
        for (int coin : coins) {
            if (coin <= rem) best = min(best, 1 + minCoins(rem - coin));
        }
        return best;
    };
    int ans = minCoins(amount);
    return ans >= INF ? -1 : ans;
}