Skip to main content

322. Coin Change

mediumAsked at eBay

eBay's payment system needs to compute optimal change breakdowns for buyer refunds — given a set of available credit denominations, what is the fewest credits needed to make a specific refund amount? Coin Change is the canonical DP formulation of this problem and is a staple eBay medium that tests bottom-up DP setup and the optimal substructure insight.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— Reported as a common eBay medium DP problem across phone screens and onsite rounds.
  • Blind (2025-11)— eBay SWE threads list Coin Change as a must-practice DP problem with practical framing in marketplace payment contexts.

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Examples

Example 1

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

Explanation: 15 = 5 + 5 + 5. Using 11 would leave a remainder of 4, needing 4 ones = 5 total — worse than three 5s.

Example 2

Input
coins = [2], amount = 3
Output
-1

Explanation: 3 cannot be formed from coin denomination 2 alone.

Example 3

Input
coins = [1], amount = 0
Output
0

Explanation: Zero amount requires zero coins.

Approaches

1. Bottom-up DP

dp[i] = minimum coins to make amount i. Initialize dp[0] = 0 and all others to Infinity. For each amount from 1 to target, try each coin: dp[i] = min(dp[i], dp[i - coin] + 1) for all valid coins.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: O(amount * n) time, O(amount) space. This is the canonical answer — clean, iterative, and easy to explain. eBay expects you to land here after articulating the DP recurrence.

2. Memoized DFS (top-down)

Recursively compute the minimum coins for the remaining amount. Memoize on the amount to avoid recomputation.

Time
O(amount * coins.length)
Space
O(amount) memo + call stack
function coinChange(coins, amount) {
  const memo = new Map();
  function dp(rem) {
    if (rem < 0) return -1;
    if (rem === 0) return 0;
    if (memo.has(rem)) return memo.get(rem);
    let min = Infinity;
    for (const coin of coins) {
      const sub = dp(rem - coin);
      if (sub !== -1) min = Math.min(min, sub + 1);
    }
    const result = min === Infinity ? -1 : min;
    memo.set(rem, result);
    return result;
  }
  return dp(amount);
}

Tradeoff: Same asymptotic complexity. More natural for those who think recursively. Extra call-stack depth can be a concern for large amounts without tail-call optimization.

eBay-specific tips

State the DP recurrence before coding: 'dp[i] = min coins to make amount i = 1 + min(dp[i - coin]) over all coins where coin <= i.' Explain why greedy fails with the classic counterexample: coins = [1, 5, 11], amount = 15. Greedy picks 11 first, leaving 4 ones = 5 coins. DP finds 3 fives = 3 coins. eBay interviewers appreciate this counter-example — it shows you understand why DP is needed here.

Common mistakes

  • Using greedy (always pick largest coin first) — fails for non-standard denominations like [1, 5, 11].
  • Not initializing dp[0] = 0 — the base case is essential; without it no dp[i] can be computed.
  • Initializing unreachable amounts as -1 instead of Infinity — makes the min comparison incorrect.
  • Off-by-one on array size — dp needs amount+1 elements (indices 0 through amount).

Follow-up questions

An interviewer at eBay may pivot to one of these next:

  • Coin Change 2 (LC 518) — count the number of distinct combinations that make up the amount (unbounded knapsack counting variant).
  • How would you reconstruct the actual coin selection, not just the count?
  • If coins are sorted and denominations are standard (1, 5, 10, 25), does greedy work? Why?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does greedy fail here?

Greedy always picks the largest coin, which is locally optimal but may not be globally optimal. With coins [1, 5, 11] and amount 15: greedy picks 11+1+1+1+1 = 5 coins, but optimal is 5+5+5 = 3 coins.

What is the time complexity?

O(amount * coins.length) — for each of the amount+1 DP states, we try each coin. With amount up to 10^4 and up to 12 coins, this is at most 120,000 operations.

What does dp[0] = 0 represent?

Zero coins are needed to make zero amount. This is the base case from which all other DP states are built transitively.

Practice these live with InterviewChamp.AI

Drill Coin Change and other eBay interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →