The Greedy Strategy
Sometimes grabbing the best option at every step gives the best overall answer — and sometimes it fails. Knowing which is the game.
The problem
You are at the cash register and owe someone $0.63 in change. You have quarters, dimes, nickels, and pennies. Without thinking, you hand over two quarters, a dime, and three pennies — six coins. You did not enumerate every possible combination of coins. You just grabbed the biggest coin that still fit, then repeated.
That instinct — take the best-looking option right now, then move on — is fast and often right. But it is not always right. Change the coins to 4 and try to make 6: your instinct grabs a 4, then needs two 1s (three coins), while the best answer is 3 + 3 (two coins). The same instinct that saved you at the register just failed. The whole skill is knowing which world you are in.
A first attempt
The safe, always-correct approach is to try everything. For coin change, that means: for each coin, either use it or skip it, and recurse on the remaining amount. Take the minimum over all branches.
def min_coins_brute(coins, amount):
if amount == 0:
return 0
best = float("inf")
for c in coins:
if c <= amount:
best = min(best, 1 + min_coins_brute(coins, amount - c))
return bestThis never lies to you — it explores every combination — but it explores an exponential number of them. For an amount n and a handful of coins, the branching blows up to roughly O(k^n). Correct, but unusable for real inputs.
The insight
The greedy shortcut says: at each step, commit to the locally best choice and never look back. For change-making, "locally best" means "the largest coin that fits". No backtracking, no exploring alternatives.
This is dramatically faster — but it is only correct when the problem has the greedy-choice property: a globally optimal solution can always be reached by making the locally optimal choice. Standard currency (25) has it. The set 4 does not. So greedy is not a universal hammer — it is a bet that pays off only when you can prove the local choice is safe.
How it works
Sort choices by "best first"
Decide what "greediest" means for your problem and order the options so the best one is easy to grab. For coins, sort descending so the largest coin comes first.
Take the best option that still fits
Scan for the first option that does not break a constraint. For change, that is the largest coin ≤ the remaining amount. Commit to it.
Reduce the problem and repeat
Subtract what you took and continue on the smaller remaining problem. Because you never revisit a choice, each step strictly shrinks the work.
Prove (or test) that local wins are safe
Before trusting the answer, argue that a locally best choice never blocks a globally best one — an exchange argument. If you cannot make that argument, greedy may silently return a worse answer.
amount = 63, coins = [25, 10, 5, 1]
63 -> take 25 -> 38 -> take 25 -> 13 -> take 10 -> 3
-> take 1 -> 2 -> take 1 -> 1 -> take 1 -> 0
result: 25 + 25 + 10 + 1 + 1 + 1 (6 coins)The code
def greedy_coins(coins, amount):
coins = sorted(coins, reverse=True)
count, used = 0, []
for c in coins:
while amount >= c:
amount -= c
count += 1
used.append(c)
return count if amount == 0 else -1 # -1: greedy could not finish
print(greedy_coins([1, 5, 10, 25], 63)) # 6function greedyCoins(coins: number[], amount: number): number {
const sorted = [...coins].sort((a, b) => b - a);
let count = 0;
for (const c of sorted) {
while (amount >= c) {
amount -= c;
count += 1;
}
}
return amount === 0 ? count : -1; // -1: greedy could not finish
}
console.log(greedyCoins([1, 5, 10, 25], 63)); // 6import java.util.Arrays;
class Greedy {
static int greedyCoins(int[] coins, int amount) {
Integer[] sorted = Arrays.stream(coins).boxed().toArray(Integer[]::new);
Arrays.sort(sorted, (a, b) -> b - a);
int count = 0;
for (int c : sorted) {
while (amount >= c) {
amount -= c;
count++;
}
}
return amount == 0 ? count : -1; // -1: greedy could not finish
}
public static void main(String[] args) {
System.out.println(greedyCoins(new int[]{1, 5, 10, 25}, 63)); // 6
}
}#include <stdio.h>
int cmp_desc(const void *a, const void *b) {
return (*(const int *)b) - (*(const int *)a);
}
int greedy_coins(int *coins, int n, int amount) {
qsort(coins, n, sizeof(int), cmp_desc);
int count = 0;
for (int i = 0; i < n; i++) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
return amount == 0 ? count : -1; /* -1: greedy could not finish */
}
int main(void) {
int coins[] = {1, 5, 10, 25};
printf("%d\n", greedy_coins(coins, 4, 63)); /* 6 */
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
int greedyCoins(std::vector<int> coins, int amount) {
std::sort(coins.begin(), coins.end(), std::greater<int>());
int count = 0;
for (int c : coins) {
while (amount >= c) {
amount -= c;
count++;
}
}
return amount == 0 ? count : -1; // -1: greedy could not finish
}
int main() {
std::cout << greedyCoins({1, 5, 10, 25}, 63) << "\n"; // 6
return 0;
}Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (try all) | O(k^n) | O(n) recursion |
| Greedy (canonical coins) | O(k log k + amount / min_coin) | O(1) |
| Sorting the choices | O(k log k) | O(1) or O(k) |
Here k is the number of distinct coins and n is the target amount. Greedy is essentially the cost of one sort plus a linear walk.
When to use it
Greedy is a bet, not a default
Reach for greedy only when you can argue the local choice is safe — via an exchange argument or a known result (like the matroid theory behind minimum spanning trees). If you cannot prove it, greedy may return a plausible-looking wrong answer with zero warning. When in doubt, dynamic programming trades speed for a guarantee of correctness.
Practice
Recap
- Greedy commits to the locally best choice at each step and never backtracks — fast, but only correct when the greedy-choice property holds.
- Prove safety with an exchange argument; when you cannot, fall back to dynamic programming.
- The same instinct that solves coin change in currency fails on 4 — recognizing the difference is the real skill.
How is this guide?
Last updated on