Skip to main content

82. Coin Change

mediumAsked at Reddit

Find the minimum number of coins to make a target amount. Reddit uses this DP problem to test classic unbounded-knapsack — the same shape used when computing minimum SQL queries to satisfy a multi-resource quota.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site DP medium.

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 (largest-first)

Always take the largest coin that fits.

Time
O(amount)
Space
O(1)
// Anti-pattern. coins=[1,3,4], amount=6 — greedy gives 4+1+1 = 3 coins; optimal is 3+3 = 2.

Tradeoff: Greedy works for canonical coin systems (US currency) but not arbitrary ones.

2. DP bottom-up (optimal)

dp[a] = min over coins c of dp[a - c] + 1. dp[0] = 0; rest start at Infinity.

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

Tradeoff: O(amount * coins). The unbounded knapsack pattern.

Reddit-specific tips

Reddit interviewers grade on whether you recognize greedy fails for arbitrary denominations. Bonus signal: provide the counterexample (coins=[1,3,4], amount=6) upfront.

Common mistakes

  • Using greedy without checking the coin set.
  • Initializing dp[0] to Infinity (must be 0 — no coins for amount 0).
  • Returning Infinity instead of -1 (problem wants -1).

Follow-up questions

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

  • Coin Change 2 (LC 518) — count combinations.
  • Perfect squares (LC 279).
  • Minimum number of coin for actual sequence.

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 is this unbounded knapsack?

Each coin can be used multiple times. Bounded knapsack would have a limited supply.

Can BFS beat DP?

BFS over states gives the same complexity. DP is cleaner for the question.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →