322. Coin Change

Q: Why initialize dp to Infinity instead of -1?

The recurrence uses Math.min, which needs a neutral upper-bound sentinel. Infinity is never a valid coin count, so any valid path naturally dominates it. -1 as a sentinel breaks min comparisons.

Q: Why is this 'unbounded' knapsack?

Unlike 0/1 knapsack where each item is used at most once, here each coin denomination can be used unlimited times. The inner loop iterates over coins (not an index into coins), allowing reuse.

Q: Can the order of loops (amount outer, coins inner) be swapped?

Yes — both orderings are correct for unbounded knapsack (same coin can be reused). If you wanted each coin at most once, you'd use items outer and amount inner (standard 0/1 knapsack order).

mediumAsked at HubSpot

HubSpot uses Coin Change to probe unbounded knapsack / bottom-up DP thinking — the same pattern that underlies their pricing-plan composer and subscription credit allocation logic, where achieving an exact amount from discrete denominations matters.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

Glassdoor (2026-Q1)— HubSpot SWE candidates report Coin Change as an onsite medium DP problem testing bottom-up tabulation.
r/cscareerquestions (2025-08)— Listed in HubSpot interview threads as a classic unbounded knapsack DP problem.

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,5,11], amount = 15

Output

Explanation: 15 = 5 + 5 + 5 (3 coins). Greedy (11+...) fails here, showing why DP is needed.

Example 2

Input

coins = [2], amount = 3

Output

-1

Explanation: Amount 3 cannot be formed with only denomination 2.

Approaches

1. Bottom-up DP

Build dp[0..amount] where dp[i] is the minimum coins needed to make amount i. dp[0] = 0. For each amount from 1 to amount, try every coin: dp[i] = min(dp[i], dp[i - coin] + 1).

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 i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: O(amount * n) time, O(amount) space. Filling the table bottom-up ensures dp[i - coin] is always computed before dp[i]. Initializing to Infinity (not -1 or 0) allows clean Math.min comparisons. This is the canonical answer.

HubSpot-specific tips

State the greedy failure case before the DP: 'Greedy (always pick the largest coin) fails for coins = [1,5,11] and amount = 15 — it picks 11+1+1+1+1 = 5 coins instead of 5+5+5 = 3.' HubSpot interviewers appreciate this motivation. Then frame the DP subproblem: 'dp[i] = minimum coins to make exactly i.' Explain why Infinity is the right sentinel — if dp[i] remains Infinity, amount i is unreachable.

Common mistakes

Initializing dp to -1 — Math.min(-1, x) = -1, which pollutes the table; use Infinity as the sentinel for unreachable.
Checking dp[i - coin] without verifying coin <= i — negative index access can produce wrong results.
Using greedy without proving it's optimal — greedy is only correct for specific coin systems (e.g., US coins); always default to DP.
Returning dp[amount] without checking Infinity — if unreachable, must return -1.

Follow-up questions

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

Coin Change II (LC 518) — count the number of combinations, not the minimum count.
What if each coin can only be used once? (0/1 knapsack variant.)
How would you reconstruct which coins were used (not just the count)?

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 initialize dp to Infinity instead of -1?

The recurrence uses Math.min, which needs a neutral upper-bound sentinel. Infinity is never a valid coin count, so any valid path naturally dominates it. -1 as a sentinel breaks min comparisons.

Why is this 'unbounded' knapsack?

Unlike 0/1 knapsack where each item is used at most once, here each coin denomination can be used unlimited times. The inner loop iterates over coins (not an index into coins), allowing reuse.

Can the order of loops (amount outer, coins inner) be swapped?

Yes — both orderings are correct for unbounded knapsack (same coin can be reused). If you wanted each coin at most once, you'd use items outer and amount inner (standard 0/1 knapsack order).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →