Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Coin Change
• Main tags: Array, Dynamic Programming, Breadth-First Search

What the problem is really asking

The input gives a set of coin denominations and a target amount. Each coin can be used as many times as needed.

The goal is not to count how many different ways the amount can be formed. The goal is to find the fewest coins needed to reach the exact amount. If the amount cannot be formed exactly, the answer is -1.

That means the real question is:

if the last coin used were c, what is the best answer for amount - c?

Once the problem is phrased that way, it becomes a shortest-path style dynamic programming problem over smaller amounts.

Why the greedy instinct fails

Many candidates first try “always take the largest coin that fits.” That feels natural, but it is not generally correct.

A simple counterexample is coins = [1, 3, 4] and amount = 6.

• A greedy choice takes 4, then 1, then 1, for a total of 3 coins.
• The optimal answer is 3 + 3, which uses only 2 coins.

So the algorithm must compare multiple ways to build the same amount rather than locking into a locally best-looking coin.

The key DP insight

Let min_coins[x] mean:

the minimum number of coins needed to make amount x

Then:

• min_coins[0] = 0 because zero coins are needed to make amount zero.
• For every positive amount x, try every coin c such that c <= x.
• If x - c is reachable, then one valid way to make x is to take the best solution for x - c and add coin c.

That gives the recurrence:

min_coins[x] = 1 + min(min_coins[x - c]) over all usable coins c

This works because every valid solution for x must end with some final coin. Once that final coin is fixed, the rest of the problem is exactly the same problem on a smaller amount.

How to derive the bottom-up solution in an interview

The clean derivation is:

1. Start with the recursive thought: “what could the last coin be?”
2. Notice that answers for the same smaller amount get reused many times.
3. Replace repeated recursion with an array from 0 up to amount.
4. Fill the array left to right so every subproblem is already solved when it is needed.

This yields a O(amount * len(coins)) solution with O(amount) extra space, which is the standard optimal answer for the usual constraints of this problem.

Why this recurrence is correct

For any target amount x, every valid solution must choose some last coin c. Removing that last coin leaves amount x - c. If the best way to make x - c uses k coins, then using coin c last makes a candidate solution for x with k + 1 coins.

Because the algorithm tries every possible last coin, it cannot miss the optimal solution. Because it only builds candidates from already-correct smaller answers, it never invents an invalid one. That is exactly why dynamic programming fits this problem so well.

Python solution

The implementation below keeps the interface simple for LeetCode, but the logic is split into small helpers so the intent stays clear. It normalizes the coin list, builds the DP table once, and returns -1 when the target amount is unreachable.

from math import inf
from typing import Iterable, List


def normalize_denominations(denominations: Iterable[int]) -> list[int]:
    """
    Return sorted, unique, positive coin denominations.

    The LeetCode input already satisfies the problem constraints, but normalizing
    the values keeps the core DP logic simpler and more defensive.
    """
    return sorted({value for value in denominations if value > 0})


def compute_minimum_coin_count(denominations: list[int], target_amount: int) -> int:
    """
    Return the fewest coins needed to reach the target amount.

    If the target amount cannot be formed exactly, return -1.
    """
    if target_amount == 0:
        return 0

    if not denominations:
        return -1

    # min_coins_for_amount[x] stores the best known answer for amount x.
    min_coins_for_amount = [0] + [inf] * target_amount

    for current_amount in range(1, target_amount + 1):
        best_count_for_current_amount = inf

        for coin_value in denominations:
            if coin_value > current_amount:
                break

            remaining_amount = current_amount - coin_value
            candidate_count = min_coins_for_amount[remaining_amount]

            if candidate_count != inf:
                best_count_for_current_amount = min(
                    best_count_for_current_amount,
                    candidate_count + 1,
                )

        min_coins_for_amount[current_amount] = best_count_for_current_amount

    final_answer = min_coins_for_amount[target_amount]
    return -1 if final_answer == inf else int(final_answer)


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        normalized_coins = normalize_denominations(coins)
        return compute_minimum_coin_count(normalized_coins, amount)

The time complexity is O(amount * number_of_coins) because each amount checks every coin once. The space complexity is O(amount) for the DP array.

Interview follow-ups

How would you return the actual set of coins, not just the count?

Store one extra array alongside the DP table to remember which coin produced the best answer for each amount. After the table is filled, start from amount and repeatedly subtract the chosen coin until reaching zero. This works because the DP table already proves that each recorded choice leads to an optimal smaller subproblem. The complexity stays O(amount * number_of_coins) time and O(amount) space, with only a small extra reconstruction cost at the end.

Could this be solved with BFS instead of dynamic programming?

Yes. Treat each reachable amount as a graph node, and from amount x add edges to x + coin for every denomination that stays within the target. Then BFS finds the minimum number of coins because every edge represents using exactly one more coin. This is a valid shortest-path formulation, and it can be intuitive in interviews. The tradeoff is that it usually has more bookkeeping than the one-dimensional DP array, so DP is typically the cleaner implementation in Python.

What changes if each coin can be used at most once?

Then this is no longer the unbounded version of the problem. The state must reflect that each coin can be chosen only once, which turns it into a 0/1 knapsack-style dynamic programming problem. A common approach is to iterate the amounts backward for each coin so one coin is not reused multiple times in the same pass. The core idea still relies on smaller subproblems, but the transition order matters much more because reuse is no longer allowed.

What if the question asked for the number of different combinations instead of the minimum number of coins?

That is a different DP definition. Instead of storing the best count of coins, store how many ways there are to build each amount. The recurrence adds counts rather than taking a minimum, and the loop order matters if the question wants combinations rather than permutations. This is why Coin Change and Coin Change II feel related but require different state meanings and different update logic.