Coin Change LeetCode Problem in Java

The Coin Change problem is a classic Dynamic Programming problem from LeetCode. Given an array of coin denominations and a target amount, the goal is to find the minimum number of coins required to make that amount. Each coin can be used any number of times. If the amount cannot be formed using the given coins, return -1.

Problem Example

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

The minimum number of coins required to make 11 is 3 because 5 + 5 + 1 = 11.

Output: 3

Important Question to Ask

At every step, we need to decide which coin to choose. If we choose a coin, the remaining problem becomes amount - coin. We repeat this process until the remaining amount becomes zero.

Brute Force Recursive Approach

The simplest approach is recursion. For the current amount, try every available coin. After choosing a coin, recursively solve the remaining amount. Among all possible choices, take the minimum number of coins.

For example, if coins are [1, 2, 5] and the amount is 11, we can choose 1, 2, or 5. If we choose 1, we solve the problem for amount 10. If we choose 2, we solve it for amount 9. If we choose 5, we solve it for amount 6.

Brute Force Recurrence

solve(amount) = 1 + min(solve(amount - coin))

The 1 represents the coin that we have just selected. We try every coin and choose the option that gives the minimum total number of coins.

Base Cases

• If amount == 0, we need 0 coins because the target has already been formed.
• If amount < 0, the current choice is invalid because we have exceeded the target amount.

Understanding the Brute Force Recursion Code

Before optimizing the Coin Change problem with Dynamic Programming, it is important to understand the recursive solution. The recursive solution follows a simple idea: choose one coin, reduce the remaining amount, recursively solve the smaller problem, and take the minimum result.

Brute Force Recursive Code

class Solution {

    public int coinChange(int[] coins, int amount) {
        int result = solve(coins, amount);

        if (result == Integer.MAX_VALUE) {
            return -1;
        }

        return result;
    }

    private int solve(int[] coins, int amount) {

        if (amount == 0) {
            return 0;
        }

        if (amount < 0) {
            return Integer.MAX_VALUE;
        }

        int minCoins = Integer.MAX_VALUE;

        for (int coin : coins) {

            int result = solve(coins, amount - coin);

            if (result != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, 1 + result);
            }
        }

        return minCoins;
    }
}

Step 1: Start from coinChange()

public int coinChange(int[] coins, int amount) {
    int result = solve(coins, amount);

    if (result == Integer.MAX_VALUE) {
        return -1;
    }

    return result;
}

The coinChange() method is the main method called by LeetCode. It passes the coins array and target amount to the recursive solve() method. The solve() method returns the minimum number of coins. If it returns Integer.MAX_VALUE, it means the target amount cannot be formed, so we return -1.

Step 2: Base Case — Amount Becomes Zero

if (amount == 0) {
    return 0;
}

This is the most important base case. If amount becomes 0, we have successfully formed the target amount. We do not need any more coins, so we return 0.

For example, if we need to make amount 5 and choose a coin of value 5, the remaining amount becomes 0. Therefore, the recursive call solve(0) returns 0.

Step 3: Invalid Amount

if (amount < 0) {
    return Integer.MAX_VALUE;
}

If the remaining amount becomes negative, the current combination is invalid. For example, if the remaining amount is 2 and we choose a coin of value 5, the new amount becomes -3. It is impossible to use this choice, so we return Integer.MAX_VALUE to represent an impossible solution.

Step 4: Initialize the Minimum

int minCoins = Integer.MAX_VALUE;

We need to find the minimum number of coins among all possible choices. Therefore, we initially set minCoins to Integer.MAX_VALUE, which represents that we have not found a valid solution yet.

Step 5: Try Every Coin

for (int coin : coins) {
    int result = solve(coins, amount - coin);

    if (result != Integer.MAX_VALUE) {
        minCoins = Math.min(minCoins, 1 + result);
    }
}

This loop is the main part of the recursion. We try every available coin. After selecting a coin, we subtract its value from the current amount and recursively solve the remaining amount.

The selected coin contributes 1 coin, and result represents the minimum number of coins required for the remaining amount. Therefore, the total number of coins is 1 + result.

Step 6: Take the Minimum

minCoins = Math.min(minCoins, 1 + result);

Different coins can produce different answers. We only need the minimum number of coins, so Math.min() keeps the best answer found so far.

Step 7: Return the Answer

return minCoins;

After trying every possible coin, minCoins contains the minimum number of coins needed to make the current amount. We return this value to the previous recursive call.

How the Recursion Works with an Example

Consider coins = [1, 2, 5] and amount = 5. The first call is solve(5). The method tries all three coins.

solve(5)
│
├── choose 1 → solve(4)
│
├── choose 2 → solve(3)
│
└── choose 5 → solve(0)
                  │
                  └── return 0

When coin 5 is selected, the remaining amount is 0. solve(0) returns 0. We then add 1 for the coin we selected, giving 1 + 0 = 1. Since this is the minimum possible answer, solve(5) eventually returns 1.

Understanding the Recursive Formula

solve(amount) = min(1 + solve(amount - coin))

This formula is the heart of the Coin Change problem. We choose a coin, which costs us 1 coin, and then solve the remaining amount. We repeat this for every available coin and choose the minimum result.

Why Does the Recursion Work?

Coin Change has optimal substructure. The minimum solution for an amount can be constructed from the minimum solution of a smaller remaining amount. If we choose coin c, then the remaining problem is amount - c. Therefore, the answer can be expressed using the answers to smaller amounts.

Why Do We Add 1?

Suppose we choose coin 5. That selected coin counts as one coin. If the recursive call says that the remaining amount requires 2 coins, then the total is 1 + 2 = 3 coins. This is why the recurrence contains 1 + result.

Why Integer.MAX_VALUE Is Used

Integer.MAX_VALUE is used as a special value to represent an impossible solution. For example, if the remaining amount becomes negative, we return Integer.MAX_VALUE. Before adding 1, we check that the result is not Integer.MAX_VALUE. This prevents integer overflow.

The Problem with This Recursion

Although the recursive solution is logically correct, it performs a lot of repeated work. For example, solve(3) may be calculated from multiple branches. Each time solve(3) is called, the entire recursion for amount 3 is executed again.

solve(5)
├── solve(4)
│   ├── solve(3)
│   └── solve(2)
│
├── solve(3)   ← repeated calculation
│
└── solve(0)

This repeated calculation is called overlapping subproblems. It is the reason the brute force recursive solution has exponential time complexity.

From Recursion to Top-Down DP

Once we identify that the same amounts are being solved repeatedly, the optimization becomes straightforward. We store the answer of solve(amount) in a dp array. The next time the same amount is requested, we return the stored value instead of running the recursion again.

if (dp[amount] != -1) {
    return dp[amount];
}

This one condition removes the repeated recursive calculations and changes the brute force recursion into Top-Down Dynamic Programming with Memoization.

Why Brute Force Is Slow

The brute force solution repeatedly solves the same subproblems. For example, solve(9) may be reached through multiple different paths. Without storing the result, solve(9) is calculated again and again.

solve(11)
   ├── solve(10)
   │      ├── solve(9)
   │      └── solve(8)
   ├── solve(9)     <- repeated
   └── solve(6)

This repeated work causes the recursive solution to have exponential time complexity.

Optimization Using Memoization

The main optimization is to remember the answer for every amount that has already been calculated. This technique is called memoization and converts the recursive solution into a Top-Down Dynamic Programming solution.

We create a dp array where dp[x] represents the minimum number of coins required to make amount x. Initially, every value is -1, which means that the amount has not been calculated yet.

Top-Down DP Idea

• Start from the target amount.
• Try every available coin.
• For a selected coin, recursively solve amount - coin.
• Add 1 for the current coin.
• Take the minimum result among all coins.
• Store the result in dp[amount].
• If the same amount is requested again, return the stored result instead of calculating it again.

DP State

The DP state is dp[amount]. It represents the minimum number of coins required to form the given amount.

Top-Down Recurrence

dp[amount] = min(1 + solve(amount - coin))
                    for every coin

We take the minimum because the problem asks for the minimum number of coins.

Coin Change Top-Down Recursive Java Solution

import java.util.Arrays;

class Solution {

    public int coinChange(int[] coins, int amount) {

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);

        int result = solve(coins, amount, dp);

        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int solve(int[] coins, int amount, int[] dp) {

        // Base case
        if (amount == 0) {
            return 0;
        }

        // Invalid case
        if (amount < 0) {
            return Integer.MAX_VALUE;
        }

        // Return already calculated result
        if (dp[amount] != -1) {
            return dp[amount];
        }

        int minCoins = Integer.MAX_VALUE;

        // Try every coin
        for (int coin : coins) {

            int result = solve(coins, amount - coin, dp);

            if (result != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, 1 + result);
            }
        }

        // Store the result
        dp[amount] = minCoins;

        return minCoins;
    }
}

How the Top-Down Solution Works

Suppose coins = [1, 2, 5] and amount = 5. We call solve(5). The algorithm tries coin 1, coin 2, and coin 5. Choosing coin 5 gives solve(0). Since solve(0) returns 0, the total becomes 1 + 0 = 1. Therefore dp[5] becomes 1.

solve(5)

coin = 1 -> 1 + solve(4)
coin = 2 -> 1 + solve(3)
coin = 5 -> 1 + solve(0)

solve(0) = 0

Therefore:
1 + solve(0) = 1

dp[5] = 1

Why Memoization Makes It Faster

There are only amount + 1 possible states: 0, 1, 2, ..., amount. Each state is calculated only once. After a state has been calculated, its answer is stored in the dp array.

For every amount, we try all available coins. If there are C coins and the target amount is A, there are A states and each state checks C coins.

Time Complexity

Let A be the target amount and C be the number of coin denominations. Each amount from 0 to A is calculated at most once, and for every amount we iterate through all C coins. Therefore, the time complexity is O(A × C).

Time Complexity: O(amount × numberOfCoins)

Space Complexity

The dp array requires O(A) space. The recursion stack can also grow up to O(A) in the worst case. Therefore, the overall auxiliary space complexity is O(A).

Space Complexity: O(amount)

Brute Force vs Top-Down DP

• Brute Force: Try every possible combination recursively.
• Brute Force Time: Approximately O(C^A) in the worst case.
• Brute Force Space: O(A) recursion stack.
• Top-Down DP: Recursion + Memoization.
• Top-Down Time: O(A × C).
• Top-Down Space: O(A).

Important Edge Cases

• If amount = 0, return 0.
• If the amount cannot be formed using any coin, return -1.
• A coin larger than the current amount should not be used for that state.
• The same coin can be used multiple times.
• Do not return Integer.MAX_VALUE + 1 because it can cause integer overflow. Check the result before adding 1.

Common Interview Mistake

A common mistake is directly calculating 1 + result when result is Integer.MAX_VALUE. Integer.MAX_VALUE represents an impossible state, and adding 1 to it causes integer overflow. Always check whether the recursive result is Integer.MAX_VALUE before adding 1.

Interview Explanation

In an interview, I would first explain the brute force recursion. For every amount, I try every coin and recursively solve the remaining amount. However, this solution has overlapping subproblems because the same amount can be calculated multiple times. To optimize it, I use memoization. I maintain dp[amount], where dp[amount] stores the minimum number of coins required to make that amount. Each state is calculated only once, and for every state I try all available coins. This gives O(amount × numberOfCoins) time complexity and O(amount) space complexity.

Key Takeaway

The main idea behind the Coin Change Top-Down DP solution is simple: choose one coin, solve the smaller remaining amount recursively, take the minimum result, and memoize it. Memoization removes repeated calculations and changes the brute force exponential solution into an O(amount × numberOfCoins) dynamic programming solution.

Frequently Asked Interview Questions

• Why does the Coin Change problem use Dynamic Programming?
• What is the DP state in Coin Change?
• What is the recurrence relation?
• Why do we need memoization?
• What is the time complexity of the Top-Down solution?
• What is the space complexity of the Top-Down solution?
• Why do we return Integer.MAX_VALUE for an impossible state?
• Why do we check Integer.MAX_VALUE before adding 1?
• What is the difference between Top-Down and Bottom-Up DP?
• Can the same coin be used multiple times?