322 — Coin Change

Problem Statement

Restating Info We’re Already Given:

• We have to find the minimum number of coins needed to create the amount only using coin values in the coins array.
• If this isn’t possible, we return 1.
• We have an infinite amount of each coin in coins.

Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):

• Should we return -1 if all coins are of greater denomination than amount?
• Are the coins sorted?

Discuss Naive Solution:

Naively, we could enumerate each coin and find the minimum of using them and keep going until we hit the base case. However, this is an exponential search space as we don’t cache intermediate results and may recalculate the same value over and over.

Discuss Optimal Solution #1:

We could do better by using Dynamic Programming. The first way we can do this is with a top-down approach. We begin by trying to determine the minimum number of coins needed to calculate amount, which leads us to the intermediate values for minimum number of coins needed to calculate amount - coin for each coin, and so on. Intermediate values are saved in minCoinsToMakeDenom and our second elif case in the helper function checks for these cached values.

Code Optimal Solution #1:

Discuss Optimal Solution #2:

We could also solve this bottom-up by building our solution up. To do so, we begin process the coins in ascending order and only denominations greater than or equal to that coin’s value since it would be pointless to use it for a smaller denomination (i.e. coin with c unit(s) currency coin is pointless if amount < c). Within the inner loop, we begin at coin because demon - coin = 0, and adding 1 = 1. This ensures that the minimum number of coins to make these denom(s) is 1 (we use that coin and are fine). Otherwise, the minimum number of coins needed for any denomination is the minimum between:

1. its current minimum number of coins needed
2. the minimum number of coins needed to get (current denomination minus the current coin) + 1.

We do this for each coin and if the final value of the last index is not infinity we can return it else return -1.

Code Optimal Solution #2:

Runtime/Space Complexity:

Both optimal solutions run in O(number of coins in coins array * amount) time and take up O(amount) space.

Test Cases:

• Test case where amount < smallest coin denomination should return -1
• Test case where no combination of coins leads us to amount should return -1
• Test case where amount is equal to one of the coins should return 1
• Test case with combination of different coins