Skip to main content

20. Coin Change

mediumAsked at Glassdoor

Glassdoor's review-scoring system aggregates weighted signals — thinking about optimal sub-amounts before building the full aggregate maps directly onto this classic DP problem they use to filter for candidates who can construct bottom-up solutions.

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

Problem

Given an integer array coins representing coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it cannot be done, return -1. You have an unlimited supply of each coin.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Examples

Example 1

Input
coins = [1,5,11], amount = 15
Output
3

Explanation: 5 + 5 + 5 = 15 uses 3 coins. Greedy (11+...) would fail here — DP is required.

Example 2

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

Explanation: No combination of 2s can reach an odd amount.

Approaches

1. Top-down recursion with memoization

Recursively compute the minimum coins for each sub-amount, caching results. Avoids recomputation; O(amount * n) overall.

Time
O(amount * n)
Space
O(amount)
function coinChange(coins, amount) {
  const memo = new Array(amount + 1).fill(-2);
  function dp(rem) {
    if (rem < 0) return -1;
    if (rem === 0) return 0;
    if (memo[rem] !== -2) return memo[rem];
    let min = Infinity;
    for (const c of coins) {
      const sub = dp(rem - c);
      if (sub !== -1) min = Math.min(min, sub + 1);
    }
    memo[rem] = min === Infinity ? -1 : min;
    return memo[rem];
  }
  return dp(amount);
}

Tradeoff:

2. Bottom-up DP (tabulation)

Build a dp array of size amount+1. For each sub-amount from 1 to amount, try every coin and take the minimum. Iterative, no stack overflow risk.

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

Tradeoff:

Glassdoor-specific tips

Glassdoor interviewers specifically set up test cases where greedy fails (e.g., coins [1,5,11], amount 15) to catch candidates who jump straight to picking the largest coin. Name the subproblem — 'minimum coins to reach each sub-amount' — before writing any code. The bottom-up table is preferred in interviews because it's easier to walk through on a whiteboard row by row.

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 Glassdoor interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →