322. Coin Change

Q: Why use Infinity instead of -1 for infeasible states in the dp array?

Math.min comparisons work cleanly with Infinity. Using -1 would require extra conditional logic to avoid taking min(-1, something), which incorrectly treats -1 as better than 0.

Q: Does order of the coin loop matter?

No — for the minimum-count problem, trying coins in any order and taking the minimum gives the same result.

Q: What is the space complexity if I use the top-down approach?

O(amount) for the memoization map plus O(amount) call-stack depth in the worst case.

mediumAsked at Anduril

Find the minimum number of coins needed to make up a given amount. Anduril uses this classic 1D DP problem to assess whether you can define the right subproblem, initialize boundary conditions correctly, and reason about infeasible states — the same structured thinking needed when minimizing resource usage in constrained mission planning.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Anduril loops.

Glassdoor (2026-Q1)— Mentioned in Anduril SWE interview prep threads as a standard unbounded-knapsack DP medium.
Blind (2025-12)— Anduril candidates describe Coin Change as a reliable DP signal problem in algorithm-heavy rounds.

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,25], amount = 36

Output

Explanation: 25 + 10 is not optimal; 25 + 10 doesn't exist. Use 25 + 10... let's recalculate: 25+5+5+1=4, actually 25+10 not possible. Optimal: 25+5+5+1=4. Wait — with [1,5,25]: 25+5+5+1=4 coins. The example uses coins=[1,5,25], showing greedy isn't always right.

Example 2

Input

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

Output

Explanation: Greedy (11+1+1+1+1) = 5 coins. DP finds 5+5+5 = 3 coins. Greedy fails here.

Example 3

Input

coins = [2], amount = 3

Output

-1

Explanation: Amount 3 cannot be formed from coin of denomination 2.

Approaches

1. Bottom-up DP

dp[i] = min coins to make amount i. For each amount from 1 to amount, try every coin and take the minimum.

Time: O(amount * coins.length)
Space: O(amount)

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // base case: 0 coins needed for amount 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). Initializing with Infinity marks infeasible states. dp[0] = 0 is the critical base case. Return -1 if dp[amount] is still Infinity after filling.

2. Top-down DP with memoization

Recursively try each coin, memoize the result for each sub-amount.

Time: O(amount * coins.length)
Space: O(amount)

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

Tradeoff: Same complexity. Top-down can be more intuitive for some candidates. Note the -1 propagation convention — infeasible is -1 in the return value but must be checked before taking min.

Anduril-specific tips

State why greedy fails first: 'With coins [1,5,11] and amount 15, greedy picks 11 then four 1s = 5 coins. DP finds 5+5+5 = 3 coins.' Anduril engineers appreciate when you immediately debunk greedy to motivate DP. Then articulate the subproblem: 'dp[i] = the minimum number of coins to make exactly i.' Use Infinity (not -1) internally to distinguish infeasible states from valid ones during computation.

Common mistakes

Initializing dp[0] to a non-zero value — dp[0] = 0 is the base case: zero coins are needed to make amount 0.
Using -1 as the sentinel for infeasibility internally — it conflates with the function's return value and causes arithmetic bugs when computing dp[i-coin] + 1.
Not checking coin <= i before accessing dp[i - coin] — negative indices cause out-of-bounds errors.
Assuming greedy works — it only works for canonical coin systems (like [1,5,10,25]); the problem doesn't guarantee this.

Follow-up questions

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

Coin Change II (LC 518) — count the number of distinct ways to make the amount.
What if you want to minimize the number of coin types used (not the total count)?
How would you reconstruct the actual coin combination used, not just the count?

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 use Infinity instead of -1 for infeasible states in the dp array?

Math.min comparisons work cleanly with Infinity. Using -1 would require extra conditional logic to avoid taking min(-1, something), which incorrectly treats -1 as better than 0.

Does order of the coin loop matter?

No — for the minimum-count problem, trying coins in any order and taking the minimum gives the same result.

What is the space complexity if I use the top-down approach?

O(amount) for the memoization map plus O(amount) call-stack depth in the worst case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →