Skip to main content

28. Coin Change

mediumAsked at Lyft

Minimize coins to reach a target — Lyft uses the same bottom-up DP to decompose a surge-pricing budget into the fewest discount tiers needed to reach a target incentive amount for driver recruitment campaigns.

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 unlimited 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,10,25], amount = 41
Output
4

Explanation: 25 + 10 + 5 + 1 = 41 using 4 coins.

Example 2

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

Approaches

1. Top-down DP (memoized recursion)

Recursively try each coin denomination, subtracting from amount. Memoize results so each sub-amount is computed once.

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 ans = dp(amount);
  return ans === Infinity ? -1 : ans;
}

Tradeoff:

2. Bottom-up DP (tabulation)

Build dp[0..amount] where dp[a] = min coins to reach a. Transition: dp[a] = min(dp[a], dp[a - coin] + 1) for each coin. Avoids recursion overhead and is cache-friendly.

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 coin of coins) {
      if (coin <= a && dp[a - coin] + 1 < dp[a]) {
        dp[a] = dp[a - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Lyft-specific tips

Lyft uses coin change as a gateway to harder DP questions about driver incentive allocation. After solving, expect a follow-up: 'How would you count the total number of ways to make amount instead of the minimum coins?' (that's the unbounded knapsack variant). Know the difference: min-coins initializes dp with Infinity; count-ways initializes dp[0] = 1 and sums rather than minimizes.

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

Practice these live with InterviewChamp.AI →