Skip to main content

322. Coin Change

mediumAsked at Juniper Networks

Find the minimum number of coins to make a target amount. Juniper uses this classic DP problem to test unbounded knapsack thinking — the same minimum-cost path logic applies to finding the minimum number of hops or minimum-cost route segments in a shortest-path calculation on a weighted network.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2025-Q4)— Reported in Juniper SWE onsite reports as a standard DP problem across multiple engineering teams.
  • Blind (2025-10)— Juniper interview prep threads frequently list Coin Change as a must-know medium 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
3

Explanation: 15 = 5 + 5 + 5 (three coins). Note: [11,1,1,1,1] uses 5 coins — the greedy approach fails here.

Example 2

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

Explanation: Cannot make 3 with only coin denomination 2.

Example 3

Input
coins = [1], amount = 0
Output
0

Explanation: Zero coins needed for amount 0.

Approaches

1. Bottom-up DP (unbounded knapsack)

dp[i] = minimum coins to make amount i. Initialize dp[0] = 0, all others to Infinity. For each amount i, try each coin: dp[i] = min(dp[i], dp[i - coin] + 1) if i >= coin.

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 * |coins|) time, O(amount) space. The standard bottom-up DP approach. Note: the greedy approach (always pick the largest coin) does NOT work for arbitrary coin sets — the DP is necessary.

Juniper Networks-specific tips

Lead with the greedy anti-example: coins = [1, 5, 11], amount = 15. Greedy picks 11 + 1 + 1 + 1 + 1 = 5 coins. DP finds 5 + 5 + 5 = 3 coins. This shows you understand why greedy fails and DP is necessary — Juniper interviewers will probe this. Draw the DP table for the example to show the derivation. The unbounded knapsack connection (each coin can be reused any number of times) is worth naming.

Common mistakes

  • Using greedy (always pick the largest coin) — provably wrong for non-canonical coin sets.
  • Initializing dp with amount + 1 as infinity — correct in theory but Infinity is cleaner and avoids overflow.
  • Forgetting the coin <= i guard — dp[i - coin] would access a negative index.
  • Returning dp[amount] directly without checking for Infinity — must return -1 if amount is unreachable.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Coin Change II (LC 518) — count the number of ways to make the amount (not the minimum).
  • Perfect Squares (LC 279) — same unbounded knapsack with coins = [1, 4, 9, 16, ...].
  • How would you find the minimum hop count from a source to a destination in a network graph?

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 work?

Greedy works for canonical coin systems (like US currency where every denomination divides the next). For arbitrary coin sets, a large coin can block a more optimal solution using smaller coins.

What is the base case?

dp[0] = 0 — zero coins are needed to make amount 0. This seeds the entire DP table.

What does 'unbounded' mean?

Each coin can be used unlimited times (unlike a 0/1 knapsack where each item is used at most once). The DP handles this because dp[i - coin] can itself include the same coin denomination.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →