Skip to main content

21. Coin Change

mediumAsked at Square

Find the minimum number of denominations to make exact change at a Square POS register — this DP problem mirrors the coin-selection logic that Square's hardware team optimizes for cash-drawer accuracy across hundreds of currency configurations.

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

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 denomination.

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
3

Explanation: 25 + 10... wait: 25 + 5 + 5 + 1 = 36 with 4 coins. Optimal: 25 + 10 — but 10 not in set. 25 + 5 + 5 + 1 = 4 coins.

Example 2

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

Example 3

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

Approaches

1. Recursion with memoization (top-down DP)

Recursively try each coin; memoize results by remaining amount. Avoids recomputing subproblems.

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 Infinity;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const c of coins) {
      best = Math.min(best, 1 + dp(rem - c));
    }
    memo.set(rem, best);
    return best;
  }
  const res = dp(amount);
  return res === Infinity ? -1 : res;
}

Tradeoff:

2. Bottom-up DP (tabulation)

Build dp[0..amount] where dp[a] = min coins for amount a. For each amount, try every coin. Clean iterative solution, no recursion stack.

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 a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a) {
        dp[a] = Math.min(dp[a], 1 + dp[a - c]);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Square-specific tips

Square uses this to verify you can reason about an unbounded knapsack without prompting. Start by stating 'this is unbounded knapsack' — that tells the interviewer you recognize the family. Then trace dp[0..5] for coins=[1,2] on the board. Square engineers care that you can explain DP state transitions in plain English to non-engineering partners, so practice saying: 'dp[a] answers: what is the fewest coins to reach exactly a?'

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →