Skip to main content

79. Coin Change

mediumAsked at Snowflake

Find the minimum number of coins that sum to a target. Snowflake asks this as the canonical 1D unbounded-knapsack — relevant to choosing min-cost combinations of cached vs cold partitions.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake compiler-team uses this for cost-DP discussion.
  • LeetCode Discuss (2025-12)— Recurring at Snowflake SDE-I onsites.

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 (broken)

Use the largest coin as much as possible.

Time
O(coins * amount)
Space
O(1)
// outline only — broken for inputs like coins = [1, 3, 4], amount = 6 (greedy gives 3, optimal is 2).

Tradeoff: Greedy is incorrect for arbitrary coin sets. Mention to reject.

2. Bottom-up DP (optimal)

dp[a] = min coins to make amount a. dp[a] = 1 + min over coin c of dp[a - c]. Base dp[0] = 0; init others to Infinity.

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

Tradeoff: Unbounded-knapsack DP. The outer loop on amount + inner on coins ensures we consider all coin choices for each subamount.

Snowflake-specific tips

Snowflake interviewers want the DP recurrence stated cleanly: dp[a] = 1 + min(dp[a-c] for c in coins where c <= a). Bonus signal: pivot to cost DP for plan selection — choosing between alternative subplans with different costs is the same min-DP shape.

Common mistakes

  • Initializing dp[0] = -1 (the 'not found' sentinel) — must be 0 for the base case.
  • Using Infinity but forgetting to check before treating dp[a-c] as a valid number.
  • Trying greedy without proving optimality for the coin set.

Follow-up questions

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

  • Coin Change II (LC 518) — count the number of ways.
  • Minimum cost to climb stairs (LC 746).
  • How does the planner choose between multiple cost-equivalent subplans?

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 isn't greedy correct?

It depends on the coin set. US coins {1, 5, 10, 25} are 'canonical' — greedy works. {1, 3, 4} isn't; greedy gives 3+1+1+1 = 4 coins for amount 6, but 3+3 = 2 coins is optimal.

How does this connect to plan costing?

Both pick the lowest-cost path to reach a target. For plan enumeration, instead of 'coins' you have 'plan alternatives', and you take the cheapest combination that produces the required output.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →