Skip to main content
Talentd

Coin Change - Solution & Explanation

MediumArrayDynamic ProgrammingBreadth-First Search19 min readAsked at: Amazon, Microsoft, Apple +37
Practice this problem

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Approach Overview

Problem Overview: Given a list of coin denominations and a target amount, compute the minimum number of coins required to make that amount. If the amount cannot be formed using the available coins, return -1. Each coin can be used unlimited times.

Approach 1: Dynamic Programming (O(n * amount) time, O(amount) space)

This problem fits the classic unbounded knapsack pattern. Build a DP array dp where dp[i] represents the minimum number of coins required to make amount i. Initialize dp[0] = 0 and set all other values to a large sentinel value. Iterate from 1 to amount, and for each value try every coin. If a coin c can contribute (i - c >= 0), update dp[i] = min(dp[i], dp[i - c] + 1). The key insight: once you know the best answer for smaller amounts, you can extend them to larger amounts. This bottom‑up table ensures each subproblem is solved exactly once. Time complexity is O(n * amount) where n is the number of coins, and space complexity is O(amount). This is the most common solution using Dynamic Programming.

Approach 2: Breadth-First Search (BFS) on Amount States (O(n * amount) time, O(amount) space)

Model the problem as a shortest-path search where each node represents a remaining amount. Start from the target amount and subtract coin values to generate new states. Each BFS level corresponds to using one additional coin. Use a queue to process states and a visited set to avoid revisiting the same remaining amount. When the search reaches 0, the current level count equals the minimum number of coins required. BFS works because every edge (adding a coin) has equal cost, so the first time you reach zero gives the optimal solution. The worst-case time complexity is O(n * amount) because each amount can be visited once and expanded by all coins. Space complexity is O(amount) for the queue and visited set. This approach is a graph perspective using Breadth-First Search and simple Array iteration over coin values.

Recommended for interviews: The bottom-up Dynamic Programming approach is what most interviewers expect. It demonstrates recognition of overlapping subproblems and optimal substructure. BFS is a solid alternative that shows you can model problems as shortest-path searches in a state graph. If you quickly mention both and implement the DP solution, you signal strong algorithmic understanding.

Approach 1: Dynamic Programming Approach

This approach dynamically computes the fewest number of coins needed for each amount from 0 to the target amount. You initialize an array dp where dp[i] represents the fewest number of coins needed to form amount i. Start with dp[0] = 0 since zero coins are needed to make the amount zero. For other amounts, assume infinity until proven otherwise. Iterate through each amount up to amount and each coin, updating dp accordingly. The solution lies in dp[amount].

This C solution uses an array dp initialized to INT_MAX except for dp[0] which is 0, signifying no coins are needed to make zero amount. For each possible amount, we iterate through each coin, updating dp[i] to be the minimum number of coins found so far that can make up i. The answer is dp[amount] unless it remains as infinity (in which case it is impossible to form the amount).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the amount and m is the number of coins.
Space Complexity: O(n), for the array dp.

Try this approach in the editor →

Approach 2: Breadth-First Search (BFS) Approach

This BFS-based method considers each step as a level, ensuring that every level in the search tree corresponds to adding a different coin denomination yielding a new amount. It is implemented using a queue initialized with the target amount, repeatedly generating the next possible amounts by subtracting each coin in turn until the amount is zero or deemed unreachable.

This BFS solution uses a queue to attempt each feasible coin subtraction on a given amount. It initially pushes a pair into the queue: the current amount, and the number of steps (or coins) taken. The iteration through coins short-circuits when next_amount becomes zero, else it appends the resulting amounts — not yet checked — back into the queue.

Code

Python

Python

Complexity

Time Complexity: Approximately O(n * m), comparable to standard BFS, where n is the amount and m is the number of coins. Actual time can be higher based on processed nodes.
Space Complexity: O(n), limited by queue and visited set sizes, corresponding to different amounts explored.

Try this approach in the editor →

Approach 3: Dynamic Programming (Complete Knapsack)

We define f[i][j] as the minimum number of coins needed to make up the amount j using the first i types of coins. Initially, f[0][0] = 0, and the values of other positions are all positive infinity.

We can enumerate the quantity k of the last coin used, then we have:

$ f[i][j] = min(f[i - 1][j], f[i - 1][j - x] + 1, cdots, f[i - 1][j - k times x] + k)

where x represents the face value of the i-th type of coin.

Let j = j - x, then we have:

f[i][j - x] = min(f[i - 1][j - x], f[i - 1][j - 2 times x] + 1, cdots, f[i - 1][j - k times x] + k - 1)

Substituting the second equation into the first one, we can get the following state transition equation:

f[i][j] = min(f[i - 1][j], f[i][j - x] + 1)

The final answer is f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n$ are the number of types of coins and the total amount, respectively.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n * m), where n is the amount and m is the number of coins.
Space Complexity: O(n), for the array dp.

Breadth-First Search (BFS) Approach

Time Complexity: Approximately O(n * m), comparable to standard BFS, where n is the amount and m is the number of coins. Actual time can be higher based on processed nodes.
Space Complexity: O(n), limited by queue and visited set sizes, corresponding to different amounts explored.

Dynamic Programming (Complete Knapsack)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (Bottom-Up)O(n * amount)O(amount)General case and most interview settings. Efficient and straightforward for unbounded coin problems.
Breadth-First Search (State Graph)O(n * amount)O(amount)Useful when modeling the problem as shortest path where each coin addition represents one step.

Video Solution

Coin Change - Dynamic Programming Bottom Up - Leetcode 322 • NeetCode • 699,070 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Coin Change easy or hard?
Coin Change is generally considered a medium difficulty problem. The challenge lies in recognizing the dynamic programming pattern and correctly defining the state transition for the minimum number of coins.
How to solve Coin Change in O(n * amount)?
Create a DP array where dp[i] represents the minimum coins needed to form amount i. Initialize dp[0] = 0 and fill the rest with a large value. For each amount i, iterate through all coins and update dp[i] = min(dp[i], dp[i - coin] + 1) if the coin fits. The final answer is dp[amount], or -1 if it remains unreachable.
What is the best approach for Coin Change?
Dynamic Programming is the most widely used solution for Coin Change. A bottom-up DP array stores the minimum coins needed for every amount from 0 to the target. This guarantees the optimal answer with O(n * amount) time and O(amount) space, where n is the number of coin denominations.
What data structure is used in Coin Change?
The most common solution uses a one-dimensional array for dynamic programming. BFS-based solutions additionally use a queue and a visited set to track explored remaining amounts during the search.
What is the time complexity of Coin Change?
The optimal dynamic programming solution runs in O(n * amount) time because each amount from 1 to the target is computed by iterating through all coin denominations. Space complexity is O(amount) for the DP array that stores intermediate results.
Coin Change Python or Java solution approach?
Both Python and Java implementations typically use the same bottom-up DP strategy. Initialize an array of size amount + 1, update values using each coin denomination, and return the computed minimum for the target amount.
Is Coin Change asked at Google, Amazon, or Meta?
Coin Change and its variations frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests understanding of dynamic programming, state transitions, and optimization over subproblems.

Ready to solve this problem?

Practice Coin Change with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count of Sub-Multisets With Bounded Sum

Next

Inverse Coin Change