Skip to main content

322. Coin Change

mediumAsked at Atlassian

Coin Change is an Atlassian-favorite dynamic programming problem. Given coin denominations and a target amount, return the fewest coins needed to make the amount, or -1 if impossible. Atlassian asks it because the bottom-up DP solution is a clean signal for whether you can write a tabular DP from a recurrence.

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

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports cite Coin Change as a recurring unbounded-knapsack-style DP problem.
  • Blind (2025-12)— Atlassian interview threads describe Coin Change as the DP problem to grade clean recurrence-to-table translation.

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 (counterexample-prone, broken)

Always pick the largest coin <= remaining amount. Works for US coins but fails on adversarial denominations.

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

Tradeoff: Wrong for general inputs — coins=[1,3,4], amount=6 returns 3 (4+1+1) instead of 2 (3+3). Show this code first so the interviewer sees you understand WHY greedy fails before you write the DP.

2. Top-down memoization

minCoins(amount) = 1 + min over coins of minCoins(amount - coin). Memoize per amount.

Time
O(amount * coins.length)
Space
O(amount)
function coinChangeMemo(coins, amount) {
  const memo = new Array(amount + 1).fill(-2);
  const solve = (rem) => {
    if (rem === 0) return 0;
    if (rem < 0) return -1;
    if (memo[rem] !== -2) return memo[rem];
    let best = -1;
    for (const coin of coins) {
      const sub = solve(rem - coin);
      if (sub !== -1) {
        if (best === -1 || sub + 1 < best) best = sub + 1;
      }
    }
    memo[rem] = best;
    return best;
  };
  return solve(amount);
}

Tradeoff: Easy to derive from the recurrence. Recursion can stack-overflow at amount=10^4 deep on degenerate inputs; ship the bottom-up version for safety.

3. Bottom-up DP (canonical)

dp[i] = min coins to make amount i. dp[0] = 0; for each i, dp[i] = 1 + min over coins of dp[i - coin] (when i - coin >= 0 and dp[i - coin] is reachable).

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

Tradeoff: The Atlassian-canonical answer. Using INF = amount + 1 instead of Infinity is the idiomatic trick — saves a floating-point comparison and the +1 never overflows back into the answer range.

Atlassian-specific tips

Atlassian uses this problem to test whether you can DEFEAT THE GREEDY INSTINCT. Spend 30 seconds writing the greedy version and the counterexample [1,3,4], amount=6 (greedy: 4+1+1 = 3, optimal: 3+3 = 2). The interviewer wants to see that you reach for DP because you know greedy is unsound here, not just because DP is your default tool. Then write the bottom-up table.

Common mistakes

  • Using Infinity as the sentinel — works but a comparison-friendly amount+1 reads cleaner.
  • Iterating coins in the outer loop and i in the inner loop — flips the semantics to 'count distinct combinations' (LeetCode 518) instead of 'fewest coins'. Watch the loop order.
  • Forgetting dp[0] = 0 — without it the whole table is unreachable.

Follow-up questions

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

  • Coin Change II (LeetCode 518) — count distinct combinations summing to amount; outer loop is coins, inner loop is amount.
  • Combination Sum (LeetCode 39) — enumerate every combination; backtracking instead of DP.
  • What if the coin supply were limited? Bounded knapsack — extra dimension for count per coin.

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 but work for US coinage?

US coins {1, 5, 10, 25} are a canonical set — greedy is provably optimal. Adversarial sets like {1, 3, 4} are not canonical, so greedy can lose. Verifying a coin set is canonical is itself NP-hard, so DP is the safe general answer.

Top-down or bottom-up at Atlassian?

Bottom-up. Lead with the recurrence, then say 'this maps to a 1D table indexed by amount'. The bottom-up version doesn't risk stack overflow and the iteration order is unambiguous. Mention memoization as 'the same recurrence as a top-down with memo'.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →