Skip to main content

83. Coin Change

mediumAsked at Datadog

Find the minimum number of coins to make a target amount. Datadog asks this for the unbounded-knapsack DP pattern — same shape as their resolution-stitching algorithm that selects the minimum number of pre-aggregated buckets to cover a query window.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — bucket-stitching analog.
  • Blind (2025-11)— Recurring at Datadog.

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 coin first)

Always take the largest coin that fits.

Time
O(amount)
Space
O(1)
// Greedy: fails on [1,3,4] amount=6 (optimal is 3+3=2 coins, greedy gives 4+1+1=3 coins).

Tradeoff: Wrong for non-canonical coin systems. Datadog will fail this.

2. Bottom-up DP (optimal)

dp[i] = min coins to make i. dp[i] = min over coins c of (dp[i-c] + 1).

Time
O(amount * coins)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(amount + 1);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

Tradeoff: O(amount * coins). The 'amount + 1' sentinel encodes 'unreachable' — anything more than amount itself is too many coins.

Datadog-specific tips

Datadog grades on whether you correctly handle the unreachable case. The amount + 1 sentinel is clean; using Infinity also works. Articulate the recurrence BEFORE coding.

Common mistakes

  • Greedy approach — wrong for non-canonical systems.
  • Using Infinity directly in JS — fine but interviewers like the sentinel trick.
  • Initializing dp[0] to something other than 0 — base case.

Follow-up questions

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

  • Coin Change II (LC 518) — count number of ways.
  • Minimum Cost for Tickets (LC 983) — coin change variant.
  • Datadog-style: stitch pre-aggregated buckets to cover a query window.

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 only for canonical coin systems (like USD). Adversarial inputs break it; DP is universal.

Why amount + 1 as sentinel?

It's strictly greater than the worst-case answer (amount coins of value 1). After DP, dp[amount] > amount means unreachable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →