Coin Change

1. Problem & Core Objective

Given coin denominations and an amount, return the fewest coins needed to make that amount. You have unlimited coins of each denomination. Return -1 if it's impossible.

coins = [1,2,5], amount = 11   →  3      5 + 5 + 1
coins = [2], amount = 3        →  -1
coins = [1], amount = 0        →  0

Constraints: 1 <= coins.length <= 12 · 1 <= coins[i] <= 2^31 − 1 · 0 <= amount <= 10^4

What's actually being tested: that greedy is wrong, and that the DP is over the amount, not over the coins. It's also the canonical unbounded knapsack — each coin may be reused, which is what makes the inner loop ascend.

2. First-Principles Thought Process

Greedy fails, and here's the counterexample

"Always take the largest coin that fits" works for real currency but not in general.

coins = [1, 3, 4], amount = 6
greedy:  4 + 1 + 1  =  3 coins
optimal: 3 + 3      =  2 coins

Taking the 4 forces two 1s. Greedy has no way to see that a locally worse choice enables a better total.

Real currency systems are deliberately designed so greedy works — that's why the intuition feels safe and isn't.

The state is the amount

dp[a] = the fewest coins summing to exactly a.

To make a, the last coin was some c from the list, leaving a − c:

dp[a] = 1 + min over all coins c <= a of dp[a − c]

Same last-move reasoning as everywhere else — what was the final decision, and what state preceded it.

The unreachable marker

Some amounts can't be made at all. Mark them with a sentinel:

Arrays.fill(dp, amount + 1);        // larger than any real answer
dp[0] = 0;

amount + 1 works because the most coins you could ever need is amount (all 1s), so it's provably unreachable as a real value — and it never overflows when you add 1 to it, unlike Integer.MAX_VALUE.

That choice of sentinel is deliberate, not arbitrary.

Why the loop order gives unlimited reuse

for (int a = 1; a <= amount; a++)
    for (int c : coins)
        if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);

dp[a - c] may itself already include coin c — nothing forbids it. That's exactly "unlimited supply", and it's why this is unbounded knapsack.

The contrast matters: in 0/1 knapsack each item is used once, which requires iterating the amount descending so an item can't be reapplied within the same pass. That's Partition Equal Subset Sum.

3. Solution Paths

Approach 1 — Greedy (wrong, worth showing)

public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int count = 0;
    for (int i = coins.length - 1; i >= 0; i--)
        while (amount >= coins[i]) { amount -= coins[i]; count++; }
    return amount == 0 ? count : -1;
}

• Time O(n log n + amount) · Correct: no

Counter-questions on this approach

⭐ "Give me an input where this fails."

coins = [1, 3, 4], amount = 6. Greedy takes 4, then can only add 1 + 1 — three coins. The optimum is 3 + 3, two coins.

The flaw is that the largest coin that fits isn't necessarily part of any optimal solution, and greedy can't reconsider.

⭐ "Why does greedy work for real currency then?"

Because denominations like [1, 5, 10, 25] are canonical — chosen so the greedy is provably optimal. That's a property of the coin system, not of the algorithm.

Verifying a system is canonical is itself non-trivial (there's a known test requiring checking amounts up to a bound). So the intuition transfers from daily experience and is unsound in general — which is exactly why this problem uses [1,3,4]-style inputs.

"Could greedy plus backtracking work?"

Yes, but that's just exhaustive search with a heuristic ordering — exponential in the worst case. The DP is O(amount × coins), which at 10^4 × 12 is 1.2 × 10^5.

Approach 2 — Memoised recursion (top-down)

public int coinChange(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, -2);                          // -2 = not yet computed
    return dp(coins, amount, memo);
}

private int dp(int[] coins, int rem, int[] memo) {
    if (rem == 0) return 0;
    if (rem < 0) return -1;                          // overshot
    if (memo[rem] != -2) return memo[rem];

    int best = Integer.MAX_VALUE;
    for (int c : coins) {
        int sub = dp(coins, rem - c, memo);
        if (sub >= 0) best = Math.min(best, sub + 1);
    }
    return memo[rem] = (best == Integer.MAX_VALUE) ? -1 : best;
}

• Time O(amount × coins) · Space O(amount) plus stack

Counter-questions on this approach

⭐ "Why is the 'not computed' sentinel -2 rather than -1 or 0?"

Because both -1 and 0 are legitimate answers: -1 means unreachable, 0 means the amount is zero. Using either as "not computed" would cause infinite recomputation of those cases.

-2 is outside the answer domain, which is the same sentinel discipline as everywhere else — verify it can't collide before relying on it.

⭐ "Why if (sub >= 0) rather than sub != -1?"

They're equivalent here since -1 is the only negative return. >= 0 reads as "a valid answer exists", which is what's meant.

The important part is that unreachable sub-amounts must not contribute — adding 1 to -1 would give 0, which looks like a free solution.

"What's the recursion depth?"

Up to amount / min(coins) = 10^4 with a coin of 1. That's deep enough to be a real stack concern in Java, which is an argument for tabulating.

Approach 3 — Tabulation (optimal)

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);                    // sentinel: bigger than any real answer
    dp[0] = 0;                                       // zero coins make zero

    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);

    return dp[amount] > amount ? -1 : dp[amount];
}

Trace — coins = [1,2,5], amount = 11:

Answer 3 ✓ (5 + 5 + 1)

• Time O(amount × coins) = 1.2 × 10^5 · Space O(amount)

Counter-questions on this approach

⭐ "Why is the sentinel amount + 1 rather than Integer.MAX_VALUE?"

Because the line dp[a - c] + 1 adds to it. Integer.MAX_VALUE + 1 overflows to Integer.MIN_VALUE, which is then smaller than everything and wins every min — silently producing garbage.

amount + 1 is provably larger than any real answer, since the worst case is amount coins of denomination 1. So dp[amount] > amount reliably means "unreachable", and adding 1 to it stays safely in range.

This is the same sentinel-arithmetic trap as Integer.MAX_VALUE in the graph problems, and here it's unavoidable rather than guardable.

⭐ "Why does the amount loop go outside and the coin loop inside?"

Because the state is the amount, and each dp[a] needs every coin considered as the possible last one. Iterating amounts outward guarantees dp[a - c] is already final when read.

Swapping the loops still works for this problem — it would compute the same minima — but it changes the meaning for the counting variant: coins-outer counts combinations, amount-outer counts permutations. That distinction is the crux of Coin Change II, so it's worth knowing the orders aren't interchangeable in general.

⭐ "Why does reusing a coin work without any special handling?"

Because dp[a - c] may itself have used coin c. Nothing prevents it, and that's exactly "unlimited supply".

The contrast is 0/1 knapsack, where each item is used once — there the amount loop must descend, so an item just applied can't be applied again in the same pass. Ascending versus descending is the entire difference between unbounded and 0/1.

"Why dp[0] = 0?"

Zero coins make amount zero. It's the base case every path bottoms out in, and it's why dp[c] = 1 comes out correctly for each denomination.

"Coins can be up to 2^31 − 1. Does that cause a problem?"

No, because if (c <= a) skips any coin larger than the current amount, and a never exceeds 10^4. So huge denominations are simply never used — they're effectively absent.

Worth checking rather than assuming, since 2^31 − 1 in the constraints looks alarming next to an amount of 10^4.

"What's the space if amount were huge?"

O(amount), and it can't be rolled — dp[a] reads dp[a - c] for every coin, and the coins can differ widely, so the lookback isn't a fixed small window. That's the counterexample to the rolling rule from question 1.

Comparison

4. Why the Optimal Wins

Greedy is wrong, not slow — [1,3,4] with amount 6 breaks it, and the intuition only feels safe because real currencies are designed to make it work.

Between the DP forms, tabulation avoids a recursion up to 10^4 deep. Both are O(amount × coins) = 1.2 × 10^5, which is trivial.

The framing worth keeping:

The state is the amount, not the coins: dp[a] = 1 + min over coins of dp[a − c]. Ascending the amount loop gives unlimited reuse — that's what makes it unbounded knapsack rather than 0/1.

And the sentinel: amount + 1, not Integer.MAX_VALUE, because the recurrence adds to it.

5. Java Prerequisites

Overflow-safe sentinel

Arrays.fill(dp, amount + 1);      // bigger than any real answer, safe to add 1 to
dp[0] = 0;
return dp[amount] > amount ? -1 : dp[amount];

Integer.MAX_VALUE would overflow at dp[a-c] + 1.

Unbounded knapsack loop order

for (int a = 1; a <= amount; a++)        // ascending -> a coin can be reused
    for (int c : coins)
        if (c <= a) dp[a] = Math.min(dp[a], dp[a-c] + 1);

0/1 knapsack descends the amount instead.

Memo sentinel — must be outside the answer domain. Here both -1 and 0 are valid answers, so -2 is the choice.

Arrays.fill is O(n) and clearer than a manual loop.

6. Interview Communication Guide

Clarifying questions: Unlimited coins of each type (yes — that's unbounded knapsack)? Can amount be 0 (yes, answer 0)? Should I return the count or the coins (count)? Are denominations distinct (assume yes; duplicates would be harmless)?

The pitch

"First, greedy is wrong, and I'd give the counterexample: coins = [1,3,4], amount = 6. Greedy takes the 4, then needs 1 + 1 — three coins. The optimum is 3 + 3, two coins. Greedy can't see that a locally worse choice enables a better total.

The intuition feels safe because real currency denominations are deliberately designed so greedy works. That's a property of the coin system, not of the algorithm.

So: DP over the amount. dp[a] is the fewest coins summing to exactly a, and the last coin was some c, leaving a − c. So dp[a] = 1 + min over coins of dp[a − c].

Two details worth stating.

The sentinel for unreachable amounts is amount + 1, not Integer.MAX_VALUE — because the recurrence does dp[a-c] + 1, and MAX_VALUE + 1 overflows to MIN_VALUE, which then wins every min and silently produces garbage. amount + 1 is provably above any real answer, since the worst case is amount coins of denomination 1.

And the amount loop ascends, which is what gives unlimited reuse — dp[a - c] may itself already contain coin c, and nothing forbids that. In 0/1 knapsack, where each item is used once, the loop descends instead so an item can't be reapplied in the same pass. Ascending versus descending is the whole difference.

O(amount × coins) = 1.2 × 10^5 here, O(amount) space.

One thing I'd check: coins can be up to 2^31 − 1, which looks alarming, but if (c <= a) skips anything bigger than the current amount — so huge denominations are simply never used."

Edge cases to volunteer:

Name [1,3,4] with amount 6. It's the greedy counterexample, and any solution that sorts and takes the largest first returns 3 instead of 2.

7. Follow-Up Questions — Modified Constraints

⭐ "Count the number of ways instead of the minimum coins."

Coin Change II. Replace min with + — counting uses addition, optimisation uses min. But now the loop order matters for correctness: coins outer counts combinations (1+2 and 2+1 are the same), amount outer counts permutations. That's the crux of that question.

⭐ "Return which coins were used."

Track the chosen coin per amount in a from[] array and walk back from amount. O(amount) extra space.

"What if each coin had limited supply?"

Bounded knapsack — add a count dimension, or use the binary-splitting trick that decomposes a supply of k into powers of two, converting it into a 0/1 knapsack with O(log k) items per coin.

"What if amount were 10^9?"

O(amount) is infeasible. With few denominations there are number-theoretic approaches (the Frobenius / Chicken McNugget problem), and for large amounts the answer becomes mostly "use the largest coin repeatedly" plus a bounded remainder — but there's no general polynomial algorithm, since the problem is NP-hard when the amount is given in binary.

"What if coins could be negative?"

The problem becomes ill-posed — you could loop indefinitely adding a positive and a negative coin to reach any amount with unbounded coin counts. The positivity constraint is what makes the DP terminate.

"Minimise the number of distinct denominations used rather than the count."

A different objective, and the state must track which denominations are in play — dp[amount][subsetOfCoins], which is O(amount × 2^12). Feasible at 12 coins, exponential in general.