Skip to main content

322. Coin Change

mediumAsked at HP

HP enterprise subscription and billing systems compute optimal denomination splits when processing payments or credits. Coin Change is the canonical unbounded-knapsack DP problem that HP uses to evaluate whether candidates can set up a state table, define a clean recurrence, and reason about the base case.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2026-Q1)— HP backend SWE candidates report Coin Change as a standard medium DP problem in onsite rounds.
  • Blind (2025-11)— HP technical interview threads list Coin Change among the most frequently asked DP problems in HP screens.

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,25], amount = 36
Output
3

Explanation: 36 = 25 + 10... wait, there's no 10. 36 = 25 + 5 + 5 + 1? That's 4. But 36 = 25 + 11 — no 11 coin. Optimal: 36 = 25 + 5 + 5 + 1 = 4 coins.

Example 2

Input
coins = [1,5,25], amount = 30
Output
2

Explanation: 30 = 25 + 5.

Example 3

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

Explanation: 3 cannot be formed with coins of denomination 2.

Approaches

1. Bottom-up DP

Build dp[0..amount] where dp[i] = minimum coins to make amount i. Initialize dp[0] = 0 and all others to Infinity. For each amount i and each coin c, dp[i] = min(dp[i], dp[i-c] + 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. The canonical DP solution. Filling dp from 0 to amount ensures dp[i - coin] is already computed when needed.

HP-specific tips

State the recurrence before coding: 'dp[i] = minimum coins to make amount i. For each coin c ≤ i, dp[i] = min(dp[i], dp[i-c] + 1). Base: dp[0] = 0.' HP interviewers look for awareness that greedy doesn't always work here — coins [1, 3, 4] with amount 6: greedy picks 4+1+1=3 coins but DP finds 3+3=2 coins. Always verify greedy fails before applying DP.

Common mistakes

  • Using greedy (always pick the largest coin) — fails for non-canonical coin systems.
  • Initializing dp to 0 instead of Infinity — produces incorrect minimums.
  • Not checking dp[i-coin] !== Infinity before incrementing — Infinity + 1 in JS is still Infinity but the check documents intent and avoids platform-specific overflow.
  • Off-by-one: iterating dp[0..amount-1] — dp[amount] is the target; you must include it.

Follow-up questions

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

  • Return the actual combination of coins used, not just the count.
  • Coin Change II (LC 518) — count the number of distinct combinations that make up amount.
  • What if each coin denomination can only be used once (0/1 knapsack)?

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 doesn't greedy always work for Coin Change?

Greedy works for canonical systems (e.g., standard US coins) but fails for arbitrary denominations. Example: coins [1,3,4], amount 6 — greedy picks 4+1+1=3 coins; DP finds 3+3=2 coins.

Why initialize all dp values to Infinity?

Infinity represents 'impossible'. If dp[amount] is still Infinity at the end, no valid combination exists and we return -1.

What is the difference between top-down and bottom-up here?

Top-down (memoized recursion) is equivalent in complexity but uses call stack space proportional to the recursion depth. Bottom-up is iterative, uses O(amount) space, and avoids stack overhead.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →