Coin Change (LeetCode #322)

Image by Dan Dennis on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Climbing Stairs.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Coin Change problem, you’re in the exact right place.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

I’m going to teach you the way to solve this one in no time flat!

Understanding the Problem 🕵🏻‍♂️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given an integer list of coins representing different amounts
2. We’ll be given an integer amount which represents the total we need to make with the coins
3. We need to find the fewest number of coins that we can use to make up the amount
4. If we can’t find a combination to make the amount, we need to return -1
5. We can assume that we have an infinite amount of each type of coin
6. The length of the coin list will be 1 <= len(coins) <= 12
7. The value of each of the coins can be 1 <= coins[i] <= 2^31 — 1
8. The amount value will be 0 < = amount <= 10^4

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s all the housekeeping items we need to discuss before we jump in.

Let’s get started!

Setup 🪚

This is one of my favorite all time coding challenges. It’s because it seems SO intimidating to come up with a fast solution at first but it’s ultimately incredibly easy once you understand the pattern.

It also gave me a really hard time when I first saw it. If that’s you right now, don’t worry; you’re going to be a pro in just a second.

The first thing we’re going to do is initialize a new tracker list that we’ll use for some dynamic programming in a second. That’s right — this is a dynamic programming question!

Here’s what this should look like:

Whoa. There’s a lot going on here.

Okay, so the first thing we’re doing is using float('inf') for the initial value in the list for each index position. This is Python’s way of writing out the maximum possible integer (other languages have this same idea).

The reason we’re doing this is because we’re going to be comparing minimum numbers in a bit and want an upper bound to ricochet against.

The next thing we’re doing up above is setting this float('inf') value for an array of length amount + 1. This is because we want our dynamic programming list to account for 0 in the first index. If we didn’t do this, our dynamic programming list would start at 1 and increase up to whatever amount is.

Make sense?

Finally, we need to set tracker[0] = 0. No matter what our other total values are at other indices, we’ll always have a total of 0 at index 0.

Make sense?

Okay, let’s get into the good stuff.

Building Out Our Loops 🔄

You might have already guessed it, but the first thing we need to do is iterate over the entire tracker list.

This is how that setup looks:

Notice here that we’re starting at index 1. This is because we’re using index 0 (which we initialized to 0 above) as the base case for our dynamic programming as we continue.

The next thing we want is (for every i in the first loop) to iterate over each of the coins in the coins list:

Inside of this loop, we want to have an if statement to check if the current i (which really just symbolizes a total that’s less than our final amount) minus the current coin c is greater-than-or-equal-to 0.

If it is, we have found a coin we can check (e.g. we don’t want to check a coin of value 10 when we’re at i of 5). We want to set the current i value in the tracker list to the minimum of either the current value or whatever tracker[i — c] + 1 is.

That tracker[i — c] + 1 bit is key here. Let’s say we’re starting out and our tracker list looks like this:

amount = 8
coins = [1, 3, 5]
tracker = [0, 'inf', 'inf', 'inf', 'inf', 'inf', 'inf', 'inf']

When we start out at index 1, we’ll be comparing the minimum of that index (which is a positive infinite value) against the value of i minus each coin if the value subtracted from i (which is 1 at the moment) is greater-than-or-equal-to 0.

The first coin, 1, satisfies this requirement. As tracker[i — c] + 1 is 1 (since tracker[i — c] is 0 here) and this value is less than 'inf', we end up setting the value of index 1 to this.

Here’s what this looks like in code form:

At each step, we’re checking the tracker[i — c] + 1 value to see if it’s less than the current value. If it is, we use that. We’re essentially looking backwards to total up the minimum necessary number of coins to continue at each step.

Pretty cool, right?

This will run right up to the last index position which will store our final answer when we’re all done.

The last thing we need to do is write our return statement. We do need to check if we never updated the final index value (which is amount) as that would mean we never found a valid total. Our ruleset said we should return -1 for that case.

Here’s what that looks like:

BOOM. Nice work. There’s our solution.

This will run in a time complexity of O(n + m) where n is the amount and m is the length of the coins list. It also has a space complexity of O(n) where n is the amount (due to our tracker list).

Conclusion

I hope this solution helped you out.

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)