LeetCode 322 - Coin Change

LeetCode Problem 322

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Breadth-First Search

Solution

Problem Understanding

The problem gives us an array called coins, where each element represents a coin denomination, and an integer called amount, which represents the target sum we want to construct.

Our goal is to determine the minimum number of coins needed to make exactly amount. We are allowed to use each coin denomination an unlimited number of times. If it is impossible to form the target amount using the available coins, we return -1.

For example, if coins = [1,2,5] and amount = 11, we can form 11 using two 5 coins and one 1 coin, for a total of 3 coins. Since no solution uses fewer than three coins, the answer is 3.

The important detail is that we are not counting the number of different combinations. Instead, we are minimizing the number of coins used.

The constraints tell us several important things:

• The number of coin types is small, at most 12
• The target amount can be as large as 10^4
• Coin values themselves can be very large

The relatively small amount limit strongly suggests that a dynamic programming solution based on building answers for all amounts from 0 to amount is feasible.

Several edge cases are important:

• amount = 0, the answer should always be 0 because no coins are needed
• Some amounts may be impossible to form, such as coins = [2] and amount = 3
• Coin denominations may be larger than the target amount
• Multiple combinations may exist, so we must ensure we choose the one using the fewest coins

A naive recursive solution can easily become extremely slow because it repeatedly recomputes the same subproblems. This overlap is the key reason dynamic programming works well here.

Approaches

Brute Force Approach

A straightforward approach is to try every possible combination of coins recursively.

For a target amount A, we can attempt to subtract every coin denomination and recursively solve the remaining subproblem. For example:

• Try using coin 1, solve for A - 1
• Try using coin 2, solve for A - 2
• Try using coin 5, solve for A - 5

We then take the minimum valid answer among all possibilities.

This approach is correct because it explores every possible combination of coins. Eventually, if a solution exists, the recursion will discover it.

However, the problem is that many subproblems are recomputed repeatedly. For example, while solving amount = 11, we may compute the answer for amount = 6 many different times from different recursive paths.

This leads to exponential time complexity, which becomes far too slow for amount values up to 10^4.

Optimal Dynamic Programming Approach

The key observation is that the problem has optimal substructure.

If we already know the minimum number of coins needed to form smaller amounts, we can use those results to compute larger amounts.

Define:

• dp[i] = minimum number of coins needed to make amount i

Then for every coin:

• If we use coin c, the remaining amount becomes i - c
• If we already know the best way to form i - c, then:

dp[i] = min(dp[i], dp[i - c] + 1)

This works because any optimal solution for amount i must end with some final coin.

We build solutions incrementally from smaller amounts to larger amounts, avoiding repeated computation entirely.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k^amount)	O(amount)	Explores all recursive combinations
Optimal Dynamic Programming	O(amount × n)	O(amount)	Builds solutions bottom up using previous results

Here:

• n = number of coin denominations
• k = branching factor in recursion

Algorithm Walkthrough

1. Create a dynamic programming array called dp of size amount + 1.

Each index represents a target amount. The value stored represents the minimum number of coins needed to form that amount. 2. Initialize all entries to a very large value.

This represents that the amount is currently unreachable. 3. Set dp[0] = 0.

Forming amount 0 requires zero coins, which serves as the base case. 4. Iterate through every amount from 1 to amount.

For each amount, we attempt to use every available coin denomination. 5. For each coin, check whether it can contribute to the current amount.

If coin <= current_amount, then we can consider using it. 6. Update the DP state.

If we use this coin, the remaining amount becomes:

current_amount - coin

Since dp[current_amount - coin] already contains the best solution for the smaller amount, we can extend it by one coin:

dp[current_amount] = min(dp[current_amount], dp[current_amount - coin] + 1) 7. Continue until all amounts are processed.

By the end, dp[amount] contains the minimum number of coins needed. 8. If dp[amount] was never updated, return -1.

Otherwise, return the stored minimum.

Why it works

The algorithm works because every solution for amount i must end with some coin c. Removing that final coin leaves amount i - c. If we already know the optimal solution for i - c, then adding one more coin produces a valid solution for i.

By considering all possible final coins and taking the minimum, we guarantee that dp[i] stores the optimal answer.

Since we process amounts from smaller to larger, every required subproblem is already solved before it is needed.

Python Solution

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Large sentinel value representing unreachable states
        INF = amount + 1

        # dp[i] = minimum coins needed to make amount i
        dp = [INF] * (amount + 1)

        # Base case
        dp[0] = 0

        # Build solutions for all amounts
        for current_amount in range(1, amount + 1):
            for coin in coins:
                if coin <= current_amount:
                    dp[current_amount] = min(
                        dp[current_amount],
                        dp[current_amount - coin] + 1
                    )

        return dp[amount] if dp[amount] != INF else -1

The implementation begins by creating a sentinel value called INF. Since the maximum number of coins needed can never exceed amount, using amount + 1 safely represents an unreachable state.

The dp array stores the minimum number of coins needed for every amount from 0 to amount.

The base case dp[0] = 0 is critical because it represents the starting point for all future computations.

The outer loop iterates through every target amount in ascending order. This guarantees that when we compute dp[current_amount], all smaller subproblems are already solved.

The inner loop tries every coin denomination. If the coin can fit into the current amount, we attempt to improve the solution using:

dp[current_amount - coin] + 1

This represents taking the best known solution for the remaining amount and adding the current coin.

Finally, if the target amount remains unreachable, we return -1.

Go Solution

func coinChange(coins []int, amount int) int {
    inf := amount + 1

    dp := make([]int, amount+1)

    for i := 1; i <= amount; i++ {
        dp[i] = inf
    }

    dp[0] = 0

    for currentAmount := 1; currentAmount <= amount; currentAmount++ {
        for _, coin := range coins {
            if coin <= currentAmount {
                candidate := dp[currentAmount-coin] + 1

                if candidate < dp[currentAmount] {
                    dp[currentAmount] = candidate
                }
            }
        }
    }

    if dp[amount] == inf {
        return -1
    }

    return dp[amount]
}

The Go implementation follows the same logic as the Python version.

One notable difference is explicit array initialization. In Go, slices default to zero values, so we manually initialize all entries except dp[0] to the sentinel value inf.

Go also does not provide a built in min function for integers in older versions, so we compare values manually before updating the DP array.

Since the constraints fit comfortably within standard integer ranges, overflow is not a concern here.

Worked Examples

Example 1

Input:

coins = [1,2,5]
amount = 11

Initial DP array:

Amount	0	1	2	3	4	5	6	7	8	9	10	11
dp	0	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

Process amount 1:

• Using coin 1
• dp[1] = dp[0] + 1 = 1

Amount	0	1
dp	0	1

Process amount 2:

• Coin 1 gives dp[1] + 1 = 2
• Coin 2 gives dp[0] + 1 = 1

Choose minimum:

Amount	0	1	2
dp	0	1	1

Continue similarly:

Amount	0	1	2	3	4	5	6	7	8	9	10	11
dp	0	1	1	2	2	1	2	2	3	3	2	3

Final answer:

3

Using coins:

5 + 5 + 1

Example 2

Input:

coins = [2]
amount = 3

DP progression:

Amount	0	1	2	3
dp	0	∞	1	∞

Amount 1 cannot be formed.

Amount 2 can be formed using one 2 coin.

Amount 3 cannot be formed because subtracting 2 leaves 1, which is unreachable.

Final answer:

-1

Example 3

Input:

coins = [1]
amount = 0

Initial state:

Amount	0
dp	0

No processing is needed because the target amount is already zero.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(amount × n)	Each amount checks every coin denomination
Space	O(amount)	DP array stores one value per amount

The algorithm processes every amount from 1 to amount. For each amount, it iterates through every coin denomination exactly once.

Since there are amount states and n coin types, the total runtime becomes:

O(amount × n)

The DP array stores one entry for every amount, giving:

O(amount)

space complexity.

Test Cases

sol = Solution()

# Provided examples
assert sol.coinChange([1, 2, 5], 11) == 3  # Standard case
assert sol.coinChange([2], 3) == -1        # Impossible amount
assert sol.coinChange([1], 0) == 0         # Zero amount

# Single coin exact match
assert sol.coinChange([7], 7) == 1         # One coin equals target

# Multiple ways, choose minimum
assert sol.coinChange([1, 3, 4], 6) == 2   # 3 + 3 is optimal

# Large unreachable amount
assert sol.coinChange([5, 10], 3) == -1    # No valid combination

# Coin larger than amount
assert sol.coinChange([10], 1) == -1       # Coin unusable

# Greedy would fail
assert sol.coinChange([1, 3, 4], 6) == 2   # DP beats greedy

# Large amount stress test
assert sol.coinChange([1, 2, 5], 100) == 20  # Twenty 5-coins

# Multiple coin types
assert sol.coinChange([2, 5, 10, 1], 27) == 4  # 10 + 10 + 5 + 2

# Repeated use of same coin
assert sol.coinChange([2], 8) == 4         # 2 + 2 + 2 + 2

Test	Why
[1,2,5], 11	Standard example with multiple denominations
[2], 3	Impossible target amount
[1], 0	Base case with zero amount
[7], 7	Exact single coin match
[1,3,4], 6	Confirms optimal rather than greedy solution
[5,10], 3	All coins larger than amount
[10], 1	Single unusable denomination
[1,2,5], 100	Stress test with larger amount
[2,5,10,1], 27	Combination of several coin types
[2], 8	Repeated use of same denomination

Edge Cases

One important edge case is when amount = 0. A common mistake is to return -1 because no coins are used. However, the correct answer is 0, since forming zero amount requires zero coins. The implementation handles this naturally by initializing dp[0] = 0.

Another important case occurs when no solution exists. For example, coins = [2] and amount = 3. Some implementations accidentally return a very large placeholder value instead of -1. This solution uses a sentinel value INF and explicitly checks whether the target remained unreachable.

A third edge case involves coins larger than the current amount. For example, if the current amount is 3 and the coin is 5, subtracting would produce a negative index. The implementation prevents this by checking:

if coin <= current_amount:

before attempting any DP transition.

A subtle case involves greedy algorithm failures. For example:

coins = [1,3,4]
amount = 6

A greedy strategy would choose 4 + 1 + 1, using three coins. The optimal solution is 3 + 3, using only two coins. Dynamic programming correctly evaluates all possibilities and guarantees the optimal answer.