IntermediateDynamic Programming
Coin Change
Problem
You are given an array coins of distinct positive coin denominations and an integer amount. Return the fewest number of coins needed to make up exactly amount. You have an unlimited supply of each coin. If the amount cannot be made, return -1.
Constraints
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2^31 - 1
- 0 ≤ amount ≤ 10^4
Examples
in: coins = [1,2,5], amount = 11
out: 3
11 = 5 + 5 + 1.
in: coins = [2], amount = 3
out: -1
What this tests
- Recognising an unbounded-knapsack style optimisation
- Defining the DP state and recurrence precisely
- Knowing why greedy fails for arbitrary denominations
- Bottom-up vs top-down and the
-1sentinel - Seeing the BFS-over-amounts equivalence
Pattern RecognitionSystematic ReasoningOptimizationEdge CasesComplexity Analysis
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Why exactly does greedy fail, and when is it safe?
F2
Count the *number of ways* to make the amount (Coin Change II).
F3
Return the actual coins used, not just the count.
F4
Each coin can be used at most once.