Skip to main content

322. Coin Change

mediumAsked at JPMorgan

Given coin denominations and a target amount, return the minimum number of coins needed (or -1 if impossible). JPMorgan asks this on SDE onsites because it is the canonical unbounded-knapsack DP — your willingness to articulate the state and transition is the grading axis.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— Recurring JPMorgan SDE onsite DP problem in 2026-Q1 reviews.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Reddit r/cscareerquestions (2025-12)— JPMC senior SDE write-up: 'asked coin change, then asked why greedy fails on [1,3,4]'.

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,2,5], amount = 11
Output
3

Explanation: 11 = 5 + 5 + 1.

Example 2

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

Example 3

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

Approaches

1. Greedy (incorrect — for discussion)

Always pick the largest coin <= remaining amount. Works for US currency [1,5,10,25] but fails in general.

Time
O(amount)
Space
O(1)
function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (const c of coins) {
    while (amount >= c) {
      amount -= c;
      count++;
    }
  }
  return amount === 0 ? count : -1;
}

Tradeoff: Linear and tempting but provably wrong on coins = [1, 3, 4], amount = 6. Greedy picks 4 + 1 + 1 = 3 coins; optimum is 3 + 3 = 2 coins. Useful to discuss why DP is needed.

2. Bottom-up DP (optimal)

dp[i] = min coins to make amount i. Initialise dp[0] = 0, dp[1..amount] = Infinity. For each i, dp[i] = 1 + min(dp[i - c]) over all coins c <= i.

Time
O(amount * |coins|)
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 c of coins) {
      if (c <= i && dp[i - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: O(amount * |coins|) time and O(amount) space — the canonical answer. The inner loop tries every coin against every subamount; the result is the true minimum because we explore all decompositions.

3. Top-down memoised recursion (equivalent but uses call stack)

Recursive solve(remaining) = 1 + min(solve(remaining - c)). Memoise on remaining.

Time
O(amount * |coins|)
Space
O(amount)
function coinChangeMemo(coins, amount) {
  const memo = new Map();
  function solve(rem) {
    if (rem < 0) return -1;
    if (rem === 0) return 0;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const c of coins) {
      const sub = solve(rem - c);
      if (sub !== -1) best = Math.min(best, sub + 1);
    }
    const ans = best === Infinity ? -1 : best;
    memo.set(rem, ans);
    return ans;
  }
  return solve(amount);
}

Tradeoff: Same asymptotic cost as bottom-up but uses O(amount) call stack. JPMorgan interviewers accept both; the iterative version is preferred because it cannot blow the stack and is easier to reason about iteration order.

JPMorgan-specific tips

JPMorgan interviewers ask 'why does greedy fail?' before they ask for code. Be ready: 'greedy works iff every coin is a multiple of the next smaller one (canonical-form currency). On non-canonical sets like [1, 3, 4], greedy can leave a small remainder that requires more 1-coins than the optimal mix. DP explores every prefix decomposition and so always finds the true minimum.' That sentence in your first 30 seconds anchors the rest of the answer.

Common mistakes

  • Initialising dp[i] = 0 instead of Infinity — produces zero answers for unreachable amounts.
  • Returning dp[amount] without the Infinity-check — wrongly returns Infinity (or NaN after arithmetic) when unreachable.
  • Looping coins in the outer loop and amount in the inner — that solves Coin Change II (count of ways), not minimum number.
  • Using greedy and then patching one edge case — there is no patchable special case; the algorithm is wrong on every non-canonical coin set.

Follow-up questions

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

  • Coin Change II (LC 518) — count the number of ways to make the amount. Same DP, different state.
  • Minimum coins where each coin can only be used once (0/1 knapsack variant).
  • What if amounts can be negative (signed change)?
  • What if the coin set is huge but the amount is small? (BFS with min-coin layer.)

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 the bottom-up DP order work?

dp[i] depends only on dp[i - c] for c in coins, all of which are strictly smaller indices. So computing dp from 0 to amount left-to-right ensures every dependency is already finalised. No revisits.

Is BFS a valid alternative?

Yes. Treat amount as a node, edges = subtract a coin. BFS finds the shortest path from amount to 0 in min coins. Same O(amount * |coins|) time, more memory because of the queue, but conceptually simpler for some candidates. Mention it if the DP framing isn't landing.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →