Skip to main content

16. Coin Change

mediumAsked at Confluent

Find the fewest coins summing to a target — Confluent uses it as the canonical unbounded knapsack to check that you reason about state transitions before extending to streaming DP over a Kafka topic.

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

Problem

Given coin denominations and an integer amount, return the fewest number of coins that sum exactly to amount, or -1 if impossible. 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,2,5], amount=11
Output
3

Example 2

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

Approaches

1. Recursive with memo

min over coins of 1 + solve(amount - coin); memoize amount.

Time
O(amount * |coins|)
Space
O(amount)
const memo=new Map();
function solve(a){ if(a<0)return Infinity; if(a===0)return 0; if(memo.has(a))return memo.get(a);
  let m=Infinity; for(const c of coins) m=Math.min(m,1+solve(a-c)); memo.set(a,m); return m; }

Tradeoff:

2. Bottom-up DP

dp[i] = min coins for amount i, base dp[0] = 0. For each i and coin <= i, dp[i] = min(dp[i], dp[i-coin]+1). Return dp[amount] or -1.

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

Tradeoff:

Confluent-specific tips

Confluent will ask how to extend DP to a stream of payments — describe how you'd checkpoint the dp[] vector per partition so exactly-once semantics survive a consumer-group rebalance without re-processing.

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

Practice these live with InterviewChamp.AI →