{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Coin Change – Solution & Complexity

Interview solutions
/
Coin Change

Solution Walkthrough

  1. Step 1: Understand the Goal

    • We need the minimum number of coins that sums exactly to amount.
    • Each coin denomination can be used unlimited times.
    • If no combination can make the amount, return -1.
    • The answer for amount 0 is 0 because no coins are needed.

  2. Step 2: Consider the Brute Force Search

    • A naive recursive solution tries every coin at every remaining amount.
    • For each choice, it solves the smaller problem remaining - coin.
    • This repeats the same remaining amounts many times, so it becomes exponential without caching.
    def coin_change(coins, amount):
    if amount == 0:
        return 0
    if amount < 0:
        return -1

    best = float('inf')
    for coin in coins:
        result = coin_change(coins, amount - coin)
        if result != -1:
            best = min(best, result + 1)

    return -1 if best == float('inf') else best

  3. Step 3: Use Dynamic Programming

    • Let dp[x] mean the fewest coins needed to make amount x.
    • We know dp[0] = 0.
    • For every amount, try each coin and reuse the already-computed answer for amount - coin.
    • This turns repeated recursive work into a table of subproblems.

  4. Step 4: Build the Table Bottom-Up

    • Initialize every amount as impossible using a large sentinel value.
    • For each target amount from 1 to amount, check every coin that fits.
    • If coin c fits, a candidate answer is dp[current - c] + 1.
    dp = [float('inf')] * (amount + 1)
dp[0] = 0

for current in range(1, amount + 1):
    for coin in coins:
        if coin <= current:
            dp[current] = min(dp[current], dp[current - coin] + 1)

  5. Step 5: Final Solution and Complexity

    • After filling the table, dp[amount] is the best answer.
    • If it is still infinity, the amount cannot be formed.
    • Time complexity is O(amount × number of coins).
    • Space complexity is O(amount).
    def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current:
                dp[current] = min(dp[current], dp[current - coin] + 1)

    return -1 if dp[amount] == float('inf') else dp[amount]

FAQ

See also

Practice Coin Change online (run code in the browser)Best Time to Buy and Sell Stock solution (easy)House Robber solution (medium)House Robber II solution (medium)Jump Game solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?