Skip to main content

322. Coin Change

mediumAsked at Cohere

Find the minimum number of coins that sum to a target amount. Cohere uses this to assess unbounded knapsack DP — the same optimisation framework underlying minimum-edit decoding and optimal token-budget allocation in constrained generation.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2025-Q4)— Cohere candidates report Coin Change as a standard medium DP problem in coding interviews.
  • Blind (2025-10)— Cohere interview threads recommend Coin Change as a representative unbounded knapsack problem to practise.

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.

Example 2

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

Explanation: No combination of coin 2 makes amount 3.

Example 3

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

Explanation: Zero coins needed for amount 0.

Approaches

1. Bottom-up DP

Build a dp array where dp[i] = minimum coins to make amount i. Initialise dp[0] = 0 and all others to Infinity. For each amount from 1 to amount, try every coin denomination.

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] + 1 < dp[i]) {
        dp[i] = dp[i - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: O(amount × n) time and O(amount) space — the canonical bottom-up DP answer. Efficient for the given constraints.

2. Top-down DP with memoisation

Recursively try subtracting each coin denomination and memoize results. Return -1 if no combination works.

Time
O(amount × coins.length)
Space
O(amount) memo + O(amount) call stack
function coinChange(coins, amount) {
  const memo = new Map();
  function dp(remaining) {
    if (remaining < 0) return -1;
    if (remaining === 0) return 0;
    if (memo.has(remaining)) return memo.get(remaining);
    let min = Infinity;
    for (const coin of coins) {
      const res = dp(remaining - coin);
      if (res !== -1) min = Math.min(min, res + 1);
    }
    const result = min === Infinity ? -1 : min;
    memo.set(remaining, result);
    return result;
  }
  return dp(amount);
}

Tradeoff: Same asymptotic complexity. More intuitive recursive structure but risks stack overflow for very large amounts. Prefer bottom-up in production.

Cohere-specific tips

Cohere interviewers appreciate the connection between Coin Change and minimum-cost token budget planning: 'Given a set of allowed token counts per call, what is the minimum number of API calls to process a document of N tokens?' This framing shows applied ML-systems thinking. Also mention that the greedy approach (always pick the largest coin) fails for many coin sets — this is why DP is necessary.

Common mistakes

  • Using greedy — fails for non-canonical coin systems (e.g., coins=[1,3,4], amount=6: greedy picks 4+1+1=3 but optimal is 3+3=2).
  • Initialising dp with 0 instead of Infinity — causes incorrect minimum calculations.
  • Returning -1 when dp[amount] > amount — use the Infinity sentinel instead of an arbitrary upper bound.
  • Not handling the amount=0 base case — should return 0 immediately.

Follow-up questions

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

  • Coin Change II (LC 518) — count the number of combinations (not minimum coins).
  • Perfect Squares (LC 279) — minimum number of perfect squares summing to n.
  • How would you adapt this for a token-budget problem where each API call can process a variable number of tokens?

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 does greedy fail for Coin Change?

Greedy works only when the coin system is canonical (each denomination is a multiple of smaller ones, like US coins). For arbitrary denominations, locally optimal choices lead to globally suboptimal solutions.

What does dp[0] = 0 represent?

Zero coins are needed to make amount 0 — the base case that all other sub-answers build on.

Is there a solution better than O(amount × n)?

For specific coin systems (e.g., powers of 2) faster solutions exist. For the general case, O(amount × n) is the known practical lower bound.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →