322. Coin Change

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 322

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 & Solution Steps

• 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 JS Solution

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];
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.