Coin Change

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.

What to notice first

• This is an optimization problem: minimize the number of coins.
• You can use each coin denomination unlimited times.
• If the amount cannot be made, return -1.
• This is a classic DP problem that can also be solved with BFS (shortest path).

Examples

coins	amount	Output	Explanation
[1,2,5]	5	1	One 5-coin makes 5
[2]	3	-1	Cannot make 3 with only 2-coins
[10]	10	1	One 10-coin makes 10
[1,3,4]	6	2	Two 3-coins or one 3-coin and three 1-coins

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

Real-World Applications

Where this pattern appears

• Currency exchange — minimizing number of bills/coins to make a payment.
• Resource allocation — using minimum resources to reach a target capacity.
• Scheduling — minimizing number of time slots to cover a duration.
• Inventory management — minimum packaging units needed for a quantity.

Complexity Comparison

Approach	Time	Space	Best For
DP	O(n * amount)	O(amount)	Classic approach, intuitive logic
BFS	O(n * amount)	O(amount)	Shortest path perspective, level-based traversal

where n = len(coins)

Which approach should you learn first?

• Pick DP if you want the fundamental dynamic programming approach.
• Pick BFS if you prefer thinking in terms of graph/shortest path problems.

Classic DP

DP Array

O(n * amount) time · O(amount) space

Graph Perspective

BFS

O(n * amount) time · O(amount) space

Approach 1: Dynamic Programming

★ Recommended

dp[i] = minimum coins needed to make amount i.

For each amount i, try all coins and pick the one that results in the minimum number of coins.

⏱ Time O(n * amount) Double loop 💾 Space O(amount) DP array

Step-by-step Example

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

amount	coin=1	coin=3	coin=4	dp[amount]
0	—	—	—	0
1	1+dp[0]=1	N/A	N/A	1
2	1+dp[1]=2	N/A	N/A	2
3	1+dp[2]=3	1+dp[0]=1	N/A	1
4	1+dp[3]=2	1+dp[1]=2	1+dp[0]=1	1
5	1+dp[4]=2	1+dp[2]=3	1+dp[1]=2	2
6	1+dp[5]=3	1+dp[3]=2	1+dp[2]=3	2

Result: dp[6] = 2 (two 3-coins)

Pseudocode

function coinChangeDP(coins, amount):
    dp = array of size amount + 1, all initialized to infinity
    dp[0] = 0

    for i from 1 to amount:
        for coin in coins:
            if coin <= i and dp[i - coin] is not infinity:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] is not infinity else -1

Solution Code

Python

coin_change_dp_array.py

from typing import List


def coin_change_dp_array(coins: List[int], amount: int) -> int:
    """
    Find minimum number of coins needed to make amount using DP array.

    Time Complexity: O(n * amount) where n = len(coins)
    Space Complexity: O(amount)

    dp[i] = minimum coins needed to make amount i
    For each amount, try all coins and take the minimum
    dp[i] = min(dp[i - coin] + 1) for all coins <= i
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

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

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


if __name__ == "__main__":
    print(coin_change_dp_array([1, 2, 5], 5))      # 1 (one 5-coin)
    print(coin_change_dp_array([2], 3))            # -1 (impossible)
    print(coin_change_dp_array([10], 10))          # 1 (one 10-coin)
    print(coin_change_dp_array([1, 3, 4], 6))      # 2 (two 3-coins or one 3-coin + three 1-coins)

C++

coin_change_dp_array.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

/**
 * Find minimum number of coins needed to make amount using DP array.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
int coinChangeDP(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins1 = {1, 2, 5};
    cout << coinChangeDP(coins1, 5) << endl;  // 1

    vector<int> coins2 = {2};
    cout << coinChangeDP(coins2, 3) << endl;  // -1

    return 0;
}

Java

CoinChangeDP.java

import java.util.*;

/**
 * Find minimum number of coins needed to make amount using DP array.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
public class CoinChangeDP {
    public static int coinChangeDP(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChangeDP(new int[]{1, 2, 5}, 5));   // 1
        System.out.println(coinChangeDP(new int[]{2}, 3));         // -1
    }
}

JavaScript

coin_change_dp_array.js

/**
 * Find minimum number of coins needed to make amount using DP array.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
function coinChangeDP(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChangeDP([1, 2, 5], 5));   // 1
console.log(coinChangeDP([2], 3));        // -1

Rust

coin_change_dp_array.rs

/**
 * Find minimum number of coins needed to make amount using DP array.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
pub fn coin_change_dp(coins: Vec<i32>, amount: i32) -> i32 {
    let amount = amount as usize;
    let mut dp = vec![i32::MAX; amount + 1];
    dp[0] = 0;

    for i in 1..=amount {
        for &coin in &coins {
            let coin = coin as usize;
            if coin <= i && dp[i - coin] != i32::MAX {
                dp[i] = dp[i].min(dp[i - coin] + 1);
            }
        }
    }

    if dp[amount] == i32::MAX {
        -1
    } else {
        dp[amount]
    }
}

fn main() {
    println!("{}", coin_change_dp(vec![1, 2, 5], 5));   // 1
    println!("{}", coin_change_dp(vec![2], 3));        // -1
}

Go

coin_change_dp_array.go

package main

import (
  "fmt"
  "math"
)

/*
 * Find minimum number of coins needed to make amount using DP array.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
func coinChangeDP(coins []int, amount int) int {
  dp := make([]int, amount+1)
  for i := 1; i <= amount; i++ {
    dp[i] = math.MaxInt32
  }
  dp[0] = 0

  for i := 1; i <= amount; i++ {
    for _, coin := range coins {
      if coin <= i && dp[i-coin] != math.MaxInt32 {
        if dp[i-coin]+1 < dp[i] {
          dp[i] = dp[i-coin] + 1
        }
      }
    }
  }

  if dp[amount] == math.MaxInt32 {
    return -1
  }
  return dp[amount]
}

func main() {
  fmt.Println(coinChangeDP([]int{1, 2, 5}, 5))   // 1
  fmt.Println(coinChangeDP([]int{2}, 3))        // -1
}

Approach 2: Breadth-First Search

🎯 Interview Favourite

Treat this as a shortest path problem: start at amount and work backward, trying each coin denomination. The first time we reach 0, we’ve found the minimum coins.

BFS explores level by level, where level k contains all amounts reachable with k coins.

⏱ Time O(n * amount) Queue and visited set 💾 Space O(amount) Visited set

Key Insight

BFS guarantees finding the shortest path (minimum coins) because it explores all possibilities at distance k before exploring at distance k+1.

Pseudocode

function coinChangeBFS(coins, amount):
    if amount == 0:
        return 0

    queue = [(amount, 0)]  # (remaining_amount, num_coins)
    visited = {amount}

    while queue is not empty:
        curr_amount, num_coins = queue.pop_front()

        for coin in coins:
            next_amount = curr_amount - coin
            if next_amount == 0:
                return num_coins + 1
            if next_amount > 0 and next_amount not in visited:
                visited.add(next_amount)
                queue.push_back((next_amount, num_coins + 1))

    return -1

Solution Code

Python

coin_change_bfs.py

from typing import List
from collections import deque


def coin_change_bfs(coins: List[int], amount: int) -> int:
    """
    Find minimum number of coins needed to make amount using BFS.

    Time Complexity: O(n * amount) where n = len(coins)
    Space Complexity: O(amount)

    Treat this as a shortest path problem in a graph:
    - Start at amount 0 (need 0 coins)
    - Each coin represents an edge to a smaller amount
    - BFS finds the shortest path to amount
    """
    if amount == 0:
        return 0

    queue = deque([(amount, 0)])  # (remaining_amount, num_coins)
    visited = {amount}

    while queue:
        current_amount, num_coins = queue.popleft()

        for coin in coins:
            next_amount = current_amount - coin
            if next_amount == 0:
                return num_coins + 1
            if next_amount > 0 and next_amount not in visited:
                visited.add(next_amount)
                queue.append((next_amount, num_coins + 1))

    return -1


if __name__ == "__main__":
    print(coin_change_bfs([1, 2, 5], 5))      # 1
    print(coin_change_bfs([2], 3))            # -1
    print(coin_change_bfs([10], 10))          # 1
    print(coin_change_bfs([1, 3, 4], 6))      # 2

C++

coin_change_bfs.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

/**
 * Find minimum number of coins needed to make amount using BFS.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
int coinChangeBFS(vector<int>& coins, int amount) {
    if (amount == 0) return 0;

    queue<pair<int, int>> q;  // (remaining_amount, num_coins)
    unordered_set<int> visited;

    q.push({amount, 0});
    visited.insert(amount);

    while (!q.empty()) {
        auto [curr_amount, num_coins] = q.front();
        q.pop();

        for (int coin : coins) {
            int next_amount = curr_amount - coin;
            if (next_amount == 0) {
                return num_coins + 1;
            }
            if (next_amount > 0 && visited.find(next_amount) == visited.end()) {
                visited.insert(next_amount);
                q.push({next_amount, num_coins + 1});
            }
        }
    }

    return -1;
}

int main() {
    vector<int> coins1 = {1, 2, 5};
    cout << coinChangeBFS(coins1, 5) << endl;  // 1

    vector<int> coins2 = {2};
    cout << coinChangeBFS(coins2, 3) << endl;  // -1

    return 0;
}

Java

CoinChangeBFS.java

import java.util.*;

/**
 * Find minimum number of coins needed to make amount using BFS.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
public class CoinChangeBFS {
    static class State {
        int amount;
        int coins;

        State(int amount, int coins) {
            this.amount = amount;
            this.coins = coins;
        }
    }

    public static int coinChangeBFS(int[] coins, int amount) {
        if (amount == 0) return 0;

        Queue<State> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(new State(amount, 0));
        visited.add(amount);

        while (!queue.isEmpty()) {
            State curr = queue.poll();

            for (int coin : coins) {
                int nextAmount = curr.amount - coin;
                if (nextAmount == 0) {
                    return curr.coins + 1;
                }
                if (nextAmount > 0 && !visited.contains(nextAmount)) {
                    visited.add(nextAmount);
                    queue.add(new State(nextAmount, curr.coins + 1));
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(coinChangeBFS(new int[]{1, 2, 5}, 5));   // 1
        System.out.println(coinChangeBFS(new int[]{2}, 3));         // -1
    }
}

JavaScript

coin_change_bfs.js

/**
 * Find minimum number of coins needed to make amount using BFS.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
function coinChangeBFS(coins, amount) {
    if (amount === 0) return 0;

    const queue = [[amount, 0]];  // [remaining_amount, num_coins]
    const visited = new Set([amount]);

    while (queue.length > 0) {
        const [currAmount, numCoins] = queue.shift();

        for (const coin of coins) {
            const nextAmount = currAmount - coin;
            if (nextAmount === 0) {
                return numCoins + 1;
            }
            if (nextAmount > 0 && !visited.has(nextAmount)) {
                visited.add(nextAmount);
                queue.push([nextAmount, numCoins + 1]);
            }
        }
    }

    return -1;
}

console.log(coinChangeBFS([1, 2, 5], 5));   // 1
console.log(coinChangeBFS([2], 3));        // -1

Rust

coin_change_bfs.rs

use std::collections::{VecDeque, HashSet};

/**
 * Find minimum number of coins needed to make amount using BFS.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
pub fn coin_change_bfs(coins: Vec<i32>, amount: i32) -> i32 {
    if amount == 0 {
        return 0;
    }

    let mut queue = VecDeque::new();
    let mut visited = HashSet::new();

    queue.push_back((amount, 0));
    visited.insert(amount);

    while let Some((curr_amount, num_coins)) = queue.pop_front() {
        for &coin in &coins {
            let next_amount = curr_amount - coin;
            if next_amount == 0 {
                return num_coins + 1;
            }
            if next_amount > 0 && !visited.contains(&next_amount) {
                visited.insert(next_amount);
                queue.push_back((next_amount, num_coins + 1));
            }
        }
    }

    -1
}

fn main() {
    println!("{}", coin_change_bfs(vec![1, 2, 5], 5));   // 1
    println!("{}", coin_change_bfs(vec![2], 3));        // -1
}

Go

coin_change_bfs.go

package main

import (
  "fmt"
)

/*
 * Find minimum number of coins needed to make amount using BFS.
 *
 * Time Complexity: O(n * amount)
 * Space Complexity: O(amount)
 */
func coinChangeBFS(coins []int, amount int) int {
  if amount == 0 {
    return 0
  }

  type state struct {
    amount   int
    numCoins int
  }

  queue := []state{{amount, 0}}
  visited := make(map[int]bool)
  visited[amount] = true

  for len(queue) > 0 {
    curr := queue[0]
    queue = queue[1:]

    for _, coin := range coins {
      nextAmount := curr.amount - coin
      if nextAmount == 0 {
        return curr.numCoins + 1
      }
      if nextAmount > 0 && !visited[nextAmount] {
        visited[nextAmount] = true
        queue = append(queue, state{nextAmount, curr.numCoins + 1})
      }
    }
  }

  return -1
}

func main() {
  fmt.Println(coinChangeBFS([]int{1, 2, 5}, 5))   // 1
  fmt.Println(coinChangeBFS([]int{2}, 3))        // -1
}

Common mistakes

Watch for these pitfalls

• Initializing dp values to 0 instead of infinity, leading to incorrect minimums.
• Forgetting to initialize dp[0] = 0 (0 coins needed to make 0 amount).
• Not checking if dp[i - coin] is valid before using it in comparisons.
• In BFS, forgetting to mark visited amounts to avoid revisiting and infinite loops.
• Returning 0 instead of -1 when amount cannot be made.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

coin_change_space_optimized.py

def solution(): return 0

C++

coin_change_space_optimized.cpp

int main() { return 0; }

Java

CoinChangeSpaceOptimized.java

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

System.out.println(new Solution().change(5, new int[]{1, 2, 5}));

JavaScript

coin_change_space_optimized.js

export default {};

Rust

coin_change_space_optimized.rs

pub fn solution() -> i32 { 0 }

Go

coin_change_space_optimized.go

package main

Related Problems

• Coin Change II ↗ Medium #518
• Combination Sum IV ↗ Medium #377
• Combination Sum ↗ Medium #39
• House Robber ↗ Medium #198

Interview Tips

Key trade-offs to discuss

• DP vs BFS: Both have the same complexity, but DP is iterative (bottom-up) and BFS is level-based. DP is typically preferred in interviews.
• Space optimization: DP uses O(amount) space. Some optimizations are possible if you only track amounts reachable with k coins, but it complicates the code.
• Reconstruction: To find the actual coins used, track the coin that resulted in each dp[i] value, then backtrack from dp[amount].
• Edge cases: amount = 0 (return 0), amount < 0 (return -1), no valid coins (return -1).

← Previous
#321 Create Maximum Number Next
#323 Number of Connected Components in an Undirected Graph →