📖 11 min read
Last updated on

Coin Change — Coding Interview Walkthrough

By intervu.dev

Hero Image for Coin Change — Coding Interview Walkthrough

You’re in a coding interview. The interviewer says: “Given a set of coin denominations and a target amount, find the minimum number of coins needed.” You know this is a DP problem. You remember the table, the recurrence, the base case. But now you need to explain why greedy fails, derive the recurrence from scratch, and justify every initialization choice while someone watches you build the solution from nothing.

This walkthrough covers the complete arc: from recursive brute force to optimal bottom-up DP, with the greedy failure explained, the recurrence derived step by step, and a model of what a polished interview performance sounds like.

The Problem

You are given an integer array coins representing coin denominations and an integer amount representing a target total. Return the fewest number of coins needed to make up that amount. If the amount cannot be made up by any combination of the given coins, return -1. You may use each coin denomination an unlimited number of times. (LeetCode #322)

Example

Input coins = [1, 5, 11], amount = 15

Output 3

The optimal combination is three coins of denomination 5 (5 + 5 + 5 = 15). Note that a greedy approach, always picking the largest coin that fits, would choose 11 first, then need four 1s to reach 15, giving a total of five coins. Greedy fails here, which is exactly why this problem requires dynamic programming. A second example: coins = [2], amount = 3 returns -1 because no combination of 2s can sum to 3.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Coin Change is a classic unbounded knapsack variant. Interviewers use it to evaluate whether you can construct a DP recurrence from scratch, handle the “impossible” case cleanly, and explain your state definition precisely before touching the keyboard.

SkillWhat Interviewers Observe
Greedy failure recognitionDo you identify why greedy doesn’t work and why DP is needed?
Recurrence formulationCan you define dp[i] clearly and derive the transition?
Base case precisionDo you correctly initialize dp[0] = 0 and all others to infinity?
Impossible case handlingDo you return -1 cleanly when dp[amount] remains infinity?
Bottom-up vs. top-down fluencyCan you implement both and explain the tradeoffs?
Complexity articulationCan you justify O(amount × len(coins)) time and O(amount) space?

Step 1: Clarifying Questions

Investing 60 seconds in clarifying questions before coding signals problem-solving maturity. Here are the most important ones for Coin Change:

  1. Can coin denominations repeat in the coins array? The problem implies distinct denominations, but confirming this avoids building logic to handle duplicates. If duplicates were present, they wouldn’t change the answer, but knowing they’re absent keeps the solution clean.

  2. Can I use each coin denomination more than once? Yes. This is an unbounded knapsack variant. Unlimited coin reuse is what makes the DP table different from a 0/1 knapsack. Confirming this distinction shows you understand the problem’s structure.

  3. What should I return if amount = 0? The answer is 0. Zero coins are needed to make zero change. This is also the DP base case. Stating this explicitly shows you’ve thought about initialization.

  4. What should I return if no combination can reach the target? Return -1. This affects how you initialize the DP table: use a sentinel value like infinity internally, then convert to -1 at the end.

  5. Are all coin values positive integers? Yes. The problem guarantees positive denominations. Confirming this avoids edge case reasoning about zero-value or negative coins that would break the DP logic.

Step 2: A First (Non-Optimal) Idea

The most natural first approach is pure recursion: to make amount, try subtracting each coin denomination and recursively solve for the remainder. Take the minimum across all choices.

def coinChange(coins, amount):
    def helper(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')  # Invalid path

        min_coins = float('inf')
        for coin in coins:
            result = helper(remaining - coin)
            if result != float('inf'):
                min_coins = min(min_coins, result + 1)
        return min_coins

    result = helper(amount)
    return result if result != float('inf') else -1

This is correct but exponentially slow: O(S^n) where S is the amount and n is the number of coins. The same subproblems get solved over and over. For amount = 100 with coins [1, 2, 5], the recursion tree fans out into billions of redundant calls.

ApproachTimeSpace
Pure recursionO(S^n) exponentialO(amount) stack
Memoized recursionO(amount × coins)O(amount)
Bottom-up DPO(amount × coins)O(amount)

The tell-tale sign: helper(10) gets called from helper(11), helper(12), helper(15), and many others, always recomputed from scratch. That’s the signal to apply memoization or reframe as bottom-up DP.

Step 3: The Key Insight

Define dp[i] as the minimum number of coins to make exactly amount i. The recurrence is: for each coin c, dp[i] = min(dp[i], dp[i - c] + 1). Use one coin of denomination c on top of the optimal solution for the remainder.

Here’s the chain of reasoning that leads to the optimal solution:

Recognize the overlapping subproblems. Every call to helper(remaining) produces the same result no matter how you got there. If you cache each subproblem result the first time it’s computed, you never recompute it. That’s memoization, and it drops the time to O(amount × len(coins)).

Flip to bottom-up for clarity and efficiency. Instead of recursing top-down and caching on the way back, build a table dp of size amount + 1 where dp[i] represents the minimum coins needed to make exactly amount i. Fill it from dp[0] up to dp[amount].

The recurrence is the heart of it. For each amount i, try every coin c. If i - c >= 0 and dp[i - c] is reachable, then dp[i] = min(dp[i], dp[i - c] + 1), one more coin on top of the optimal solution for the remainder.

Initialization is critical. Set dp[0] = 0 (zero coins to make zero). Set all other entries to float('inf') as a sentinel meaning “not yet reachable.” At the end, if dp[amount] is still infinity, return -1.

The verbal framing matters here: don’t just say “use DP.” Say “I’m building up the answer for every sub-amount from 0 to the target, and for each one I’m asking: which coin, if I used it last, gives me the fewest total coins?”

DP array of length 12 for coins=[1,2,5], amount=11. dp[11]=3 highlighted. Shows minimum coins for each sub-amount. ---

Step 4: Optimal Strategy

Here’s the bottom-up DP algorithm, step by step:

  1. Create a list dp of size amount + 1, initialized entirely to float('inf').
  2. Set dp[0] = 0, the base case: zero coins needed to reach amount zero.
  3. Iterate i from 1 to amount (inclusive).
  4. For each coin denomination c in coins:
    • If c <= i (the coin doesn’t overshoot), check if dp[i - c] + 1 < dp[i].
    • If so, update dp[i] = dp[i - c] + 1.
  5. After filling the table, check dp[amount].
  6. If dp[amount] is still float('inf'), return -1. Otherwise, return dp[amount].

The order of iteration matters here: filling dp[i] requires dp[i - c] to already be computed, which is guaranteed since we process smaller amounts first.

Python Implementation

def coinChange(coins: list[int], amount: int) -> int:
    # dp[i] = minimum coins needed to make exactly amount i
    # Initialize to infinity to represent "not yet reachable"
    dp = [float('inf')] * (amount + 1)

    # Base case: 0 coins needed to make amount 0
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                # Using this coin gives us dp[i - coin] + 1 total coins
                dp[i] = min(dp[i], dp[i - coin] + 1)

    # If dp[amount] is still infinity, no valid combination exists
    return dp[amount] if dp[amount] != float('inf') else -1

Style notes worth calling out in an interview:

  • Initializing dp to float('inf') rather than -1 or 0 is deliberate. It acts as a sentinel for “unreachable,” and the min() operation naturally ignores unreachable states without special-casing.
  • The guard dp[i - coin] != float('inf') prevents building on unreachable sub-amounts. Omitting it would leave dp[i] as inf + 1, which is still inf in Python but signals unclear thinking.
  • The nested loop order (outer over amounts, inner over coins) is the standard unbounded knapsack pattern. Swapping them would still work here since coins are unbounded, but the current order is clearer and more conventional.
  • Converting float('inf') to -1 only at the final return keeps all internal logic clean and uniform.

For completeness, here’s the top-down memoized version, useful to present as the stepping stone:

from functools import lru_cache

def coinChange(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        return min(dp(remaining - c) + 1 for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

Time & Space Complexity

OperationComplexity
TimeO(amount × len(coins))
SpaceO(amount)

Time: The outer loop runs amount times. For each sub-amount, the inner loop iterates over all len(coins) denominations. Every operation inside is O(1). Total: O(amount × len(coins)).

Space: The dp array has amount + 1 entries. No other data structures scale with input size. Space is O(amount).

A common follow-up: “Can you do better than O(amount × len(coins))?” The honest answer is no. This is essentially optimal for the general case. You can prune with early termination in practice, but the asymptotic bound holds. Saying this confidently demonstrates genuine understanding of the algorithm’s limits.

Common Interview Mistakes

  1. Reaching for greedy first without questioning it. Greedy (always use the largest coin that fits) works for standard coin systems like US currency, but fails for arbitrary denominations. Candidates who implement greedy without questioning it signal they haven’t thought critically about the problem structure. Always justify why DP is needed.

  2. Initializing dp to 0 instead of infinity. If dp[i] starts at 0, the min() operation will always return 0, never updating to the real answer. The infinity sentinel is essential, not a minor implementation detail.

  3. Forgetting the dp[0] = 0 base case. Without it, no amount greater than zero can ever be reached, because every path back to zero would find dp[0] = inf and halt. The base case is what seeds the entire table.

  4. Off-by-one in the loop range. Using range(1, amount) instead of range(1, amount + 1) skips computing dp[amount], the very value you need. Always double-check loop bounds with a small example.

  5. Not handling the impossible case. Returning dp[amount] directly without checking for infinity yields a confusing large number instead of -1. The final conversion is not optional.

  6. Confusing unbounded vs. 0/1 knapsack. In this problem, each coin can be used unlimited times. That’s why dp[i - coin] is safe to use in a forward-filling loop. If each coin could only be used once, the loop order and state definition would change. Mentioning this distinction earns points.

  7. Not articulating the recurrence before coding. The DP table means nothing without a clear state definition. Before writing a single line, say: “dp[i] is the minimum coins to make amount i, and dp[i] = min(dp[i - c] + 1) for each valid coin c.” Candidates who skip this and go straight to code look like they’re transcribing a memorized solution.

What a Strong Candidate Sounds Like

“My first instinct is recursion: to make amount, try each coin and recursively solve the remainder, taking the minimum. That gives the right answer but it’s exponential because I’m recomputing the same sub-amounts over and over.

That’s the signal for DP. I’ll define dp[i] as the minimum number of coins to make exactly amount i. The recurrence is: for each coin c, dp[i] = min(dp[i], dp[i - c] + 1), use one coin of denomination c on top of the optimal solution for the remainder.

Base case: dp[0] = 0. Everything else starts at infinity, unreachable until proven otherwise. I fill the table bottom-up from 1 to amount. At the end, if dp[amount] is still infinity, no solution exists and I return -1.

Time is O(amount × number of coins), space is O(amount). Let me trace through coins = [1, 5, 11], amount = 15 to verify before I code it.”

Example Interview Dialogue

Interviewer: Given coin denominations and a target amount, find the minimum number of coins needed.

Candidate: A couple of questions first. Can I use each denomination unlimited times? And should I return -1 if the amount is unreachable?

Interviewer: Yes to both.

Candidate: Good. I want to flag that greedy doesn’t work here. For [1, 5, 11] and target 15, greedy picks 11 then four 1s for five coins, but three 5s is optimal. So I need DP. I’ll build a table dp where dp[i] is the minimum coins to make amount i. For each amount from 1 to the target, I try every coin and update: dp[i] = min(dp[i], dp[i - coin] + 1).

Interviewer: How do you initialize the table?

Candidate: dp[0] = 0, zero coins to make zero. Everything else starts at infinity as a sentinel for “not yet reachable.” At the end, if dp[amount] is still infinity, I return -1. The infinity initialization is critical. If I used 0, the min() would always return 0 and never update.

Interviewer: What’s the time and space complexity?

Candidate: Time is O(amount × len(coins)), two nested loops, each O(1) per iteration. Space is O(amount) for the DP table. No better asymptotic bound is known for the general case.

Interviewer: How would you modify this to return the actual coins used, not just the count?

Candidate: I’d add a second array parent of size amount + 1. When I update dp[i], I record parent[i] = coin, the denomination that achieved the optimal. At the end, I backtrack: start at amount, follow parent[amount] to get the last coin used, subtract it, repeat until I reach 0. That reconstructs the full coin list in O(amount) additional time and space.

Coin Change is the gateway to the broader knapsack and DP-on-values problem family. These problems share the same bottom-up table-filling pattern:

  • Coin Change II (LeetCode #518). Instead of minimum coins, count the number of ways to make the amount. Same table, different recurrence.
  • Climbing Stairs (LeetCode #70). The simplest Fibonacci-style DP. Coin Change is the generalized version with arbitrary “step sizes.”
  • House Robber (LeetCode #198). 1D DP where each state depends on earlier states, same build-from-base-case structure.
  • Word Break (LeetCode #139). DP on string positions instead of amounts. Same “can I reach this state from a valid earlier state?” pattern.
  • Perfect Squares (LeetCode #279). Minimum number of perfect squares summing to n. Structurally identical to Coin Change with coins as squares.

The jump from Coin Change to Coin Change II (#518) is one of the most common interview progressions. The table shape is the same, but the recurrence changes from min to summation, and the loop order matters for avoiding duplicate combinations. Being ready for that follow-up is a strong signal.

Practice This in a Mock Interview

This walkthrough gives you the full mental model: greedy failure, recurrence derivation, initialization logic, and complexity analysis. But DP problems have a specific failure mode in live interviews. Candidates who understood the solution perfectly in study sessions find themselves staring at a blank table, unsure whether to initialize with 0 or infinity, unsure whether the loop goes amount then coins or coins then amount.

Those doubts don’t disappear from reading. They disappear from doing. The only way to make DP feel reliable under pressure is to write it out, narrate it, and answer follow-up questions repeatedly, with feedback.

Start a mock interview for Coin Change on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →