LeetCode 322. Coin Change — Python Solution

Blind 75 — Programming & Technical Interview Questions — Explanation Series

The problem:

The explanation:

Originally I thought this solution was easy, sort the coins and then just work your way backwards from largest coin to smallest until the amount is 0. The problem with this solution is maybe the amount is larger than the biggest coin, but you cannot reach 0 if the largest coin is used. This is where the problem becomes more complex. Using a bottom-up dynamic programming technique works best. You can work from $.01 (the amount is a cent total not dollar total) all the way to the amount and then for each whole dollar go through each coin and if the coin is less than or equal to the amount, add one more coin to the total coins used to get to the previous amount. After this loop, return the minimum amount of coins to add to this amount.

The Dynamic Programming Solution: O(n * k)

First create the array that is used to keep track of minimum amount of coins needed to sum to the amount. Set every index in this array to the amount plus one. This is used during the return statement to check if the coins can sum to the amount as well as determining the minimum amount of coins…