Coin Change Amazon Python Interview Question

You are given an integer array coins representing of different denominations and an integer 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 = [2, 4, 1, 4], target_amount = 5

Output: 2

Explanation:
There are several combinations to make up the amount , such as:

1. using five 1's (1 + 1 + 1 + 1 + 1)
2. using three 1's and one 2 (1 + 1 + 1 + 2)
3. using two 2's and one 1 (2 + 2 + 1)
4. using one 4 and one 1 (4 + 1)

The combination that uses the fewest coins is the last one (using and ), which totals 2 coins.

Example #2

Input: coins = [2], target_amount = 3

Output: -1

Explanation:
It is impossible to make up the amount using only the coin , since cannot be combined in any way to reach . Therefore, the output is .

Brute Force (Recursive)

This approach explores all possible ways to reach the by either:

1. Including the current coin and moving closer to the target amount.
2. Skipping the current coin and moving to the next one in the list.

Since we don’t know which combination of coins will yield the minimum count, we try all options recursively and pick the smallest valid result.

Base Cases:

1. If equals , we return because no more coins are needed.
2. If we run out of coins or exceeds , we return infinity () to mark this path as invalid.

Recursive Cases:

1. Choose the current coin by adding it to the and incrementing the count.
2. Skip the current coin and move to the next one in the list.

Here’s the code:

Iterative Solution

Intuition

Think of each coin as a building block for constructing an amount. If you’re trying to make an amount using a coin of value , the remaining portion to be constructed is . If you already know the minimum number of coins needed to make the smaller amount (), you can just add 1 to include the current coin.

For example:

• If you know it takes 2 coins to make , then it would take coins to make with the current coin.

By repeating this process for all coins and all amounts up to the target amount, we can determine the minimum number of coins needed for each value.

Approach

We’ll use an array to keep track of the minimum number of coins needed to make each amount from to the target amount. Here’s the plan:

1. Create an array of size , where each index represents an amount. Set all values to infinity (), except which is (since it takes zero coins to make an amount of ).

2. For each coin in the list, check if it can contribute to constructing amounts starting from its value up to the target amount.

3. For each amount that the coin can contribute to, calculate the number of coins needed:

   • Use the coins already counted for the remaining portion ().
   • Update with the minimum value between the current value and the newly calculated value ().

4. If the value at remains infinity, it means it’s impossible to make the target amount, so return .

Here is the code: