322. Coin Change

At a Glance

Topic: dp-1d
Pattern: Dynamic Programming (unbounded knapsack: minimum count)
Difficulty: Medium
Companies: Google, Amazon, Microsoft, Oracle, Apple
Frequency: Very High
LeetCode: 322

Problem (one-liner)

Given positive coin values (infinite each) and target amount, return the minimum number of coins to sum to amount, or -1 if impossible. Input: coins, amount. Output: int.

Recognition Cues

“Unlimited coins” + “minimum number to make amount”
Classic unbounded knapsack with min objective
Order of processing coins does not change min count for this formulation

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — BFS/DFS on amounts — very large fan-out.
Better — BFS on graph of amounts (also O(amount * coins) in worst case).
Optimal — 1D DP: minCoins[sum] = min over coins — O(amount * len(coins)) time / O(amount) space. <- pick this in interview.

Optimal Solution

Go

package main

import "math"

func coinChangeTable(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}
	const sentinel = math.MaxInt32
	dp := make([]int, amount+1)
	for sum := 1; sum <= amount; sum++ {
		dp[sum] = sentinel
	}
	dp[0] = 0
	for sum := 1; sum <= amount; sum++ {
		for _, coin := range coins {
			if coin <= sum && dp[sum-coin] != sentinel {
				candidate := dp[sum-coin] + 1
				if candidate < dp[sum] {
					dp[sum] = candidate
				}
			}
		}
	}
	if dp[amount] == sentinel {
		return -1
	}
	return dp[amount]
}

func coinChangeCoinOuter(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}
	const sentinel = math.MaxInt32
	minCoins := make([]int, amount+1)
	for sum := 1; sum <= amount; sum++ {
		minCoins[sum] = sentinel
	}
	minCoins[0] = 0
	for _, coin := range coins {
		for sum := coin; sum <= amount; sum++ {
			if minCoins[sum-coin] != sentinel {
				candidate := minCoins[sum-coin] + 1
				if candidate < minCoins[sum] {
					minCoins[sum] = candidate
				}
			}
		}
	}
	if minCoins[amount] == sentinel {
		return -1
	}
	return minCoins[amount]
}

func coinChange(coins []int, amount int) int {
	return coinChangeCoinOuter(coins, amount)
}

JavaScript

function coinChangeTable(coins, amount) {
	if (amount === 0) return 0;
	const sentinel = Number.POSITIVE_INFINITY;
	const dp = new Array(amount + 1).fill(sentinel);
	dp[0] = 0;
	for (let sum = 1; sum <= amount; sum++) {
		for (const coin of coins) {
			if (coin <= sum && dp[sum - coin] !== sentinel) {
				dp[sum] = Math.min(dp[sum], dp[sum - coin] + 1);
			}
		}
	}
	return dp[amount] === sentinel ? -1 : dp[amount];
}

function coinChange(coins, amount) {
	if (amount === 0) return 0;
	const sentinel = Number.POSITIVE_INFINITY;
	const minBySum = new Array(amount + 1).fill(sentinel);
	minBySum[0] = 0;
	for (const coin of coins) {
		for (let sum = coin; sum <= amount; sum++) {
			if (minBySum[sum - coin] !== sentinel) {
				minBySum[sum] = Math.min(minBySum[sum], minBySum[sum - coin] + 1);
			}
		}
	}
	return minBySum[amount] === sentinel ? -1 : minBySum[amount];
}