Coin Change Visualization for Coding Interviews
Min coins to make amount; 1D DP with coin choices.
Concept
Coin Change is the 'make exact change with the fewest coins' problem: given a set of coin denominations and an amount, find the minimum number of coins (of any denomination, reused freely) that sum to that amount, or report that no combination works. It generalizes to unbounded knapsack and shows up in currency vending machines, DNA motif counting, and shortest-path problems on small alphabets. A naive recursion is exponential, memoization brings it to O(amount * denominations), and the iterative bottom-up DP is the cleanest implementation. A related sibling problem counts the total number of ways to make change rather than the minimum coins — the recurrence differs in an important way (iteration order of coins vs amount) that catches many interviewees.
How it works
Let dp[a] be the minimum number of coins that sum to a, with dp[0] = 0 as the base case. For each amount a from 1 to the target, try every coin c: if c <= a and dp[a - c] is reachable, then dp[a] = min(dp[a], dp[a - c] + 1). Use a sentinel like Integer.MAX_VALUE or amount + 1 to mark unreachable cells — this sentinel must be checked before adding 1 to avoid integer overflow. After the table is filled, dp[amount] is the answer, or -1 if it equals the sentinel. The outer loop iterates amount, the inner loop iterates coins; because a coin can be used any number of times, the recurrence reads from dp[a - c] which may already reflect earlier uses of the same coin. For the ways-to-make-change variant the structure flips: dp[a] counts combinations, outer loop iterates coins, inner loop iterates amount ascending. Iterating the other way would count permutations, not combinations. Reconstruction is a backward walk: while amount > 0, find a coin c such that dp[amount - c] = dp[amount] - 1, emit c, subtract, repeat.
Implementation
import java.util.Arrays;
public final class CoinChange {
private CoinChange() {}
public static int coinChange(int[] coins, int amount) {
if (amount < 0) return -1;
int sentinel = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, sentinel);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
}
}
}
return dp[amount] == sentinel ? -1 : dp[amount];
}
public static int[] coinChangeWithPicks(int[] coins, int amount) {
int sentinel = amount + 1;
int[] dp = new int[amount + 1];
int[] choice = new int[amount + 1];
Arrays.fill(dp, sentinel);
Arrays.fill(choice, -1);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
choice[a] = c;
}
}
}
if (dp[amount] == sentinel) return new int[0];
int[] picks = new int[dp[amount]];
int idx = 0, rem = amount;
while (rem > 0) { picks[idx++] = choice[rem]; rem -= choice[rem]; }
return picks;
}
}
Complexity
- Time:
O(amount * |coins|) - Space:
O(amount)
Common pitfalls
- Using Integer.MAX_VALUE as sentinel and adding 1 without checking — overflow to negative.
- Applying a greedy 'always take the largest coin' — only correct for canonical systems like USD.
- Confusing 'min coins' with 'number of ways'; the latter needs a different loop order.
- Forgetting to return -1 when amount cannot be made — returning amount + 1 is wrong.
- Indexing coins array negatively when c > a — guard the subtraction.
Key design decisions & trade-offs
- DP vs greedy — Chosen: DP for arbitrary denominations. Greedy fails on non-canonical coin sets; DP always finds the optimum.
- Top-down memoization vs bottom-up — Chosen: Bottom-up for cache locality. Bottom-up is iterative and avoids recursion stack on large amounts.
- Exact vs approximate — Chosen: Exact DP up to amount ~10^7. Beyond that memory and time dominate; use BFS on residues for sparse coin sets.
Practice problems
Interview follow-ups
- Solve the 'number of ways' variant — note the different loop order.
- Treat coin change as unbounded knapsack and compare the recurrence.
- Implement a BFS solution treating coins as edge weights on a graph of amounts.
- Extend to a bounded version where each coin has a maximum usable count.
Why it matters
Coin Change is a core part of the Dynamic Programming toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".