Skip to main content

322. Coin Change

mediumAsked at Akamai

Find the minimum number of coins to make a given amount. Akamai uses this to probe classic unbounded knapsack DP — the same recurrence structure appears in packet fragmentation optimization where the goal is to minimize the number of segments needed to transmit a payload of a given size.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE interview reports list Coin Change as a representative DP problem in algorithm-focused onsite rounds.
  • Blind (2025-10)— Akamai threads confirm dynamic programming problems including Coin Change appear frequently in second-round interviews.

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 = 30
Output
2

Explanation: 25 + 5 = 30, two coins.

Example 2

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

Explanation: Cannot make 3 with only denomination 2.

Example 3

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

Explanation: Zero coins needed for amount 0.

Approaches

1. Bottom-up DP

Build dp[0..amount] where dp[i] = minimum coins to make amount i. Initialize to Infinity, set dp[0] = 0. For each amount, try each 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;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        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 solution. The inner loop order (amounts outer, coins inner) gives the unbounded knapsack flavor — each coin can be used multiple times.

2. BFS (level = number of coins used)

Start from amount 0. Each BFS level corresponds to adding one more coin. The first level at which we reach the target amount is the answer.

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  if (amount === 0) return 0;
  const visited = new Set([0]);
  let queue = [0];
  let steps = 0;
  while (queue.length) {
    steps++;
    const next = [];
    for (const curr of queue) {
      for (const coin of coins) {
        const val = curr + coin;
        if (val === amount) return steps;
        if (val < amount && !visited.has(val)) {
          visited.add(val);
          next.push(val);
        }
      }
    }
    queue = next;
  }
  return -1;
}

Tradeoff: Also O(amount * n). BFS guarantees the minimum depth (fewest coins) is found first. Interesting framing, but the DP approach is more standard and expected at Akamai.

Akamai-specific tips

State the recurrence before coding: 'dp[i] = min over all coins c where c <= i of (dp[i - c] + 1). Base case dp[0] = 0 — zero coins for zero amount.' Akamai interviewers appreciate the unbounded knapsack connection: 'This differs from 0/1 knapsack because each coin can be used unlimited times — so we don't track per-item usage.' The -1 sentinel (return -1 if dp[amount] remains Infinity) is a common mistake point; mention it.

Common mistakes

  • Forgetting to return -1 when dp[amount] is Infinity — the problem requires -1, not Infinity, when no solution exists.
  • Confusing with 0/1 knapsack — here each denomination is available infinitely, so no per-item tracking is needed.
  • Not checking coin <= i before dp[i - coin] — accessing a negative index wraps around in some implementations.

Follow-up questions

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

  • Coin Change II (LC 518) — count the number of combinations (not minimum count) that make the amount.
  • How does the complexity change if the coin denominations are very large (up to 2^31)?
  • Can you solve it with a greedy approach? When does greedy fail (e.g., coins = [1,3,4], amount = 6)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

When does a greedy (largest coin first) approach fail?

With coins = [1,3,4] and amount = 6: greedy picks 4 + 1 + 1 = 3 coins, but DP finds 3 + 3 = 2 coins. Greedy requires canonical coin systems (like US currency) to be optimal.

Why initialize dp to Infinity instead of -1?

Infinity acts as a sentinel for 'unreachable'. We then compute dp[i] = min(dp[i], dp[i-coin]+1) cleanly. Using -1 would require special-casing the min comparison.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →