Coin Change

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonGoogleBloomberg

A cashier has an unlimited supply of coins in several denominations and owes a customer a specific amount of change. Working out the minimum number of coins the cashier could hand over — using each denomination as many times as needed — is the goal; if the denominations available simply can't add up to that exact amount, the answer should signal that paying it precisely is impossible. Handing over nothing at all pays off an amount of zero — that's the natural stopping point every path eventually reaches. Whenever a positive amount is still owed, picking any single denomination as the next coin handed over leaves a smaller remaining amount that faces the identical question all over again. Since a denomination isn't used up after being picked once, it stays available to be picked again on the very next step. Trying every denomination at every remaining amount, and keeping track of whichever choice leads to the fewest coins overall, builds up the answer from the smallest amounts toward the full one.

Test Case 1:

Input:coins = [2, 5, 7], amount = 12

Output:2

Explanation:5 + 7 = 12 using just 2 coins, fewer than any other combination.

Test Case 2:

Input:coins = [3], amount = 7

Output:-1

Explanation:Every multiple of 3 (0, 3, 6, 9, ...) skips over 7, so no combination of 3s ever reaches it.

Test Case 3:

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

Output:2

Explanation:3 + 3 = 6 (or equivalently other 2-coin combinations), and no single coin equals 6.

Constraints

◆1 ≤ coins.length ≤ 15
◆1 ≤ coins[i] ≤ 100
◆0 ≤ amount ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Reaching a remaining amount of 0 takes 0 more coins — that's the finish line. For any positive amount still owed, try every coin denomination as the next one used: each choice reduces the amount by that coin's value and costs one coin, so the best count from here is 1 plus whatever the best count turns out to be for the reduced amount. Since coins can be reused freely, the same coin can be tried again immediately in the next call. An amount that goes negative, or that no combination can ever reach, is treated as impossible and excluded from the comparison; the smallest count found across every coin tried is the answer for that amount.

TimeO(coins^amount)

SpaceO(amount)

Java

Try it out

class Solution {
    private int[] coins;

    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        int result = solve(amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int solve(int remaining) {
        if (remaining == 0) return 0;
        if (remaining < 0) return Integer.MAX_VALUE;
        int best = Integer.MAX_VALUE;
        for (int c : coins) {
            int sub = solve(remaining - c);
            if (sub != Integer.MAX_VALUE) best = Math.min(best, 1 + sub);
        }
        return best;
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for every amount from 0 up to the target, the fewest coins needed to make it exactly — starting from dp[0] = 0 coins needed for nothing. For every later amount, trying each coin denomination that fits gives a candidate count: 1 plus whatever the fewest coins is for the amount left over after using that coin, provided that smaller amount is itself reachable at all. The smallest candidate across every coin becomes that amount's answer. Because smaller amounts are always filled in before larger ones need them, every lookup is already resolved, and the entry at the full amount holds the final answer — or stays unreachable if no combination of coins ever lands on it exactly.

TimeO(coins.length × amount)