Log inSign up
mediumLeetCodeNot Started

Coin Change

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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.

### Example 1 - Input: coins = [1, 2, 5], amount = 11 - Output: 3 - Explanation: 11 = 5 + 5 + 1 (3 coins).

### Example 2 - Input: coins = [2], amount = 3 - Output: -1 - Explanation: Amount 3 cannot be formed using only coin 2.

### Example 3 - Input: coins = [1], amount = 0 - Output: 0

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Unbounded Knapsack recurrence under minimization constraints.
  • Understand why a sentinel value (e.g. amount + 1) is safer than integer MAX_VALUE to prevent overflow.
  • Implement space-optimal O(amount) forward tabulation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Unlimited supply of denominations.
  • Target sum to achieve.
  • Minimize the total count of items picked.

Algorithmic Decision Tree:

  • Unbounded reuse -> forward DP loop over amounts.
  • Minimization -> default initialize with infinity.

Connected Patterns:

Coin Change IIPerfect SquaresMinimum Cost For Tickets

1. Recursive DFS Exhaustion

Intuition

At each step, try subtracting every coin denomination and recurse on the remaining balance.

Algorithm

  1. Define dfs(rem).
  2. If rem == 0, return 0.
  3. If rem < 0, return infinity.
  4. Initialize minCoins = infinity.
  5. For each coin c in coins: minCoins = min(minCoins, 1 + dfs(rem - c)).
  6. Return minCoins.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int dfs(int rem, const vector<int>& coins) {
8 if (rem == 0) return 0;
9 if (rem < 0) return 1e9;
10
11 int minCoins = 1e9;
12 for (int c : coins) {
13 int res = dfs(rem - c, coins);
14 if (res != 1e9) {
15 minCoins = min(minCoins, 1 + res);
16 }
17 }
18 return minCoins;
19}
20
21int coinChangeRec(vector<int>& coins, int amount) {
22 int ans = dfs(amount, coins);
23 return ans >= 1e9 ? -1 : ans;
24}
25
26int main() {
27 vector<int> coins = {1, 2, 5};
28 int amount = 11;
29 cout << "Fewest coins (Recursive): " << coinChangeRec(coins, amount) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(S^n) where S is amount and n is coins.length
  • Space complexity: O(S) recursion stack

2. Top-Down Memoized DP

Intuition

Cache the results for each sub-amount in a memo array of size amount + 1.

Algorithm

  1. Initialize memo array of size amount + 1 filled with -2.
  2. Define helper solve(rem): if rem == 0 return 0; if rem < 0 return -1.
  3. If memo[rem] != -2, return memo[rem].
  4. Find min over all valid coins: minC = 1 + solve(rem - c).
  5. Store result in memo[rem] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int solveMemo(int rem, const vector<int>& coins, vector<int>& memo) {
8 if (rem == 0) return 0;
9 if (rem < 0) return -1;
10 if (memo[rem] != -2) return memo[rem];
11
12 int minCoins = 1e9;
13 for (int c : coins) {
14 int res = solveMemo(rem - c, coins, memo);
15 if (res >= 0) {
16 minCoins = min(minCoins, 1 + res);
17 }
18 }
19 return memo[rem] = (minCoins == 1e9 ? -1 : minCoins);
20}
21
22int coinChangeMemo(vector<int>& coins, int amount) {
23 vector<int> memo(amount + 1, -2);
24 return solveMemo(amount, coins, memo);
25}
26
27int main() {
28 vector<int> coins = {1, 2, 5};
29 int amount = 11;
30 cout << "Fewest coins (Memoized): " << coinChangeMemo(coins, amount) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(amount * coins.length)
  • Space complexity: O(amount) memo table and call stack

3. Bottom-Up Iterative 1D DP Tabulation

Intuition

Build an array dp of size amount + 1 filled with amount + 1. Iteratively compute each amount from 1 to amount.

Algorithm

  1. Create array dp of size amount + 1 filled with amount + 1.
  2. dp[0] = 0.
  3. For a = 1 to amount:
  4. For each coin c in coins:
  5. If c <= a: dp[a] = min(dp[a], 1 + dp[a - c]).
  6. Return dp[amount] > amount ? -1 : dp[amount].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int coinChangeOptimal(vector<int>& coins, int amount) {
8 vector<int> dp(amount + 1, amount + 1);
9 dp[0] = 0;
10
11 for (int a = 1; a <= amount; a++) {
12 for (int c : coins) {
13 if (c <= a) {
14 dp[a] = min(dp[a], 1 + dp[a - c]);
15 }
16 }
17 }
18 return dp[amount] > amount ? -1 : dp[amount];
19}
20
21int main() {
22 vector<int> coins = {1, 2, 5};
23 int amount = 11;
24 cout << "Fewest coins (Optimal DP): " << coinChangeOptimal(coins, amount) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(amount * coins.length)
  • Space complexity: O(amount) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(S^n)O(S)Recursively try every coin at each step.Redundant sub-amount calculations
2.Top-Down Memoized DPO(S * n)O(S)Cache intermediate minimums in array.Recursion depth
3.Bottom-Up Iterative DPOptimalO(S * n)O(S)1D array filled forwards from amount 1 to S.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using greedy (picking largest coin first): Fails for inputs like coins = [1, 3, 4, 5], amount = 7 where greedy picks 5+1+1 (3 coins) instead of 4+3 (2 coins).

Pitfall 2:

Integer overflow when adding 1 to INT_MAX.

Crucial Edge Cases to Validate:

  • amount = 0: Output is 0.
  • Cannot form amount: Output is -1.
  • Coins larger than amount: Output is -1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always emphasize why greedy fails: give a counterexample like coins=[1, 3, 4], amount=6 (greedy takes 4, 1, 1 = 3 coins, but optimal is 3, 3 = 2 coins).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we initialize the dp array with amount + 1 instead of Integer.MAX_VALUE?

Back to DSA Sheet