Coin Change

6 days ago
5 min read

Coin Change looks innocent. Just coins and a target amount. But this problem forces you to be precise about what you're optimizing, how you build solutions, and how you detect when something is impossible. That makes it a staple in technical interviews.

Problem Statement

You are given an integer array coins representing coin denominations and an integer amount representing a total amount of money.

Return the fewest number of coins needed to make up that amount.If the amount cannot be made up by any combination of the coins, return -1.

You may assume you have an infinite number of each type of coin.

1. Clarify Requirements Before Jumping Into Code

Before coding, let's make sure we understand the rules.

Input:
- coins: array of positive integers
- amount: non-negative integer
Output:
- Minimum number of coins needed
- -1 if it’s impossible
Coins can be reused unlimited times
Order of coins does not matter

Edge questions I’d mentally check:

What if amount = 0? Then I need 0 coins.
What if coins is empty?
Are coin values always positive? In interviews, yes.

2. Identify the Category of the Question

So two key points point to this question being a Dynamic Programming problem. The first is the fact that we have many possible solutions and we need to optimize. Optimization problems often involve DP. The second point is the fact that the solution to larger target values may somehow involve the solutions to smaller targets. In other words, it sounds like we have overlapping subproblems, which is a hallmark of DP.

Common patterns for DP include:

Tabulation, i.e. bottoms-up storing of results to smaller subproblems
Memoization, i.e. top-down caching of results to smaller subproblems

3. Consider a Brute-Force Approach to Understand the Problem

The brute-force idea is to try every possible combination of coins that sums to amount.

That means:

For each coin, either use it or move on
Recurse until the sum matches or exceeds the target

This explodes fast.

Time complexity: O(C^a), where C is the number of coins and A is the target amount
Space complexity: recursion depth up to amount

It helps me understand the decision tree, but it’s completely impractical.

4. Brainstorm More Solutions

Let's think through some alternative solutions.

We can simplify the problem a bit by imagining the question: what would be the minimum number of coins required to build up the smallest possible amount?

Let's think through this with the US system of coins. We have pennies (value of 1), nickels (5), dimes (10) and quarters (25).

If my target amount is 1, well then obviously my solution is 1 - I need one penny to reach my amount. And we can count up for target amounts 2 (2 pennies), 3 (3 pennies), and 4 (4 pennies).

So far this thought process is pointing me towards one of the standard solutions for DP problems: a bottoms-up array, one where I am storing the minimum number of coins required to make a target amount of i.

Things get more interesting at i=5. I can reach that target two ways - either with five pennies or with one nickel. Obviously one nickel is the best solution here. And for i=6 through i=9, we know the best solutions are going to be one nickel plus some number of pennies.

But how do we abstract that into a more general solution that we can apply for any combination of coins and amounts? What lessons can we take away by walking through our example?

The first lesson is that for every step in our DP array, we can't just check one coin - we have to check every available coin to see if it will be useful in our solution.

For these small examples, that has meant only focusing on the smallest coins. But what if the value is big enough that multiple coin values can be used in our solution, like in i=8?

We are already checking every possible coin to see if it should be included in our solution, but let's ask ourselves, with each coin, what other piece of data are we missing to finish our solution?

What we're missing is the minimum number of coins required to achieve the remainder after subtracting each coin from our target amount. Or to turn that into an equation, what we need is the minimum number of coins required to reach i (our current target amount) - C (the current coin we are checking).

For example, if i=8 and we are checking C=5 (a nickel), then we need to know what is the minimum number of coins required to achieve a target of 8 - 5, or 3.

And here's the key realization - we already know the answer to that thanks to our DP array!

So our solution for target amount i = dp[i - c] + 1 (for the current coin)

Now let's try and formalize that into an algorithm.

Let dp[i] represent the minimum number of coins needed to make amount i.

For any amount i, we try every coin:

If we use coin c, then we need to know dp[i - c]
If dp[i - c] is valid, then dp[i] = dp[i - c] + 1

This finds the minimum over all possible coins.

But we also need a way to detect when a solution for a particular amount and set of coins is “impossible”. For example, there is no solution for a target amount of 1 if your smallest coin has a value of 5.

There are any number of ways you can do this, and we'll leave it up to you to pick your favorite. Depending on your preferred coding language, this may be an opportunity to show off your mastery of that language!

Since we are finding minimums, it makes sense to me to set a default value for every element in the array to some arbitrarily large value. Then I can make use of Java's min function.

Final approach recap:

Use a DP array of size amount + 1
Initialize with a sentinel value
Build solutions bottom-up

5. Discuss Trade-Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute-force recursion	Exponential	O(amount)	Simple conceptually	Completely infeasible
Top-down memoization	O(amount × coins)	O(amount)	Intuitive recursion	Stack overhead
Bottom-up DP	O(amount × coins)	O(amount)	Predictable, iterative	Uses extra memory

6. Write Pseudocode to Structure Your Thoughts

dp[0] = 0
for i from 1 to amount:
    dp[i] = infinity
    for each coin in coins:
        if i - coin >= 0:
            dp[i] = min(dp[i], dp[i - coin] + 1)

if dp[amount] is infinity:
    return -1
return dp[amount]

7. Consider Edge Cases

I explicitly think through:

amount = 0 → return 0
coins is empty → return -1 unless amount is 0
Amounts that cannot be formed at all
Large amounts → ensure time complexity is acceptable

The DP setup naturally handles these.

8. Write Full Code Syntax

public class CoinChange {

    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE)

        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

9. Test Your Code

System.out.println(coinChange(new int[]{1, 2, 5}, 11)); // 3
System.out.println(coinChange(new int[]{2}, 3));       // -1
System.out.println(coinChange(new int[]{1}, 0));       // 0
System.out.println(coinChange(new int[]{1}, 2));       // 2
System.out.println(coinChange(new int[]{186, 419, 83, 408}, 6249)); // 20

These tests cover:

Standard cases
Impossible cases
Zero amount
Larger inputs

10. Key Lessons to Remember for Future Questions

When the goal is to minimize or maximize something, think DP.
Finding a solution can often start by thinking through an example.
Simplify a tough problem by thinking about the smallest possible example and then slowly adding in complexity with larger values

Good Luck and Happy Coding!