Greedy Algorithm Mistakes: Four That Break Code That Looks Correct
- Greedy isn't proven by passing examples: the exchange argument is what validates a greedy strategy — if swapping the greedy choice can never improve the result, the algorithm is correct
- Wrong sort key is the most common culprit: interval scheduling needs end-time sort, not start-time; LeetCode 179 needs a concatenation comparator, not numeric sort
- One word changes the algorithm: fractional knapsack is O(n log n) greedy, 0/1 knapsack needs DP — the difference is whether items can be divided
- Two trackers beat O(n²) simulation: Gas Station's O(n) solution hinges on a skip-failed-segments invariant, with one variable for global feasibility and one for local progress
- Adversarial test cases reveal greedy bugs: test identical elements, reversed order, and one locally-optimal-but-dead-end element before committing to any greedy approach
- Run the diagnostic before you write a line: name the greedy choice, verify the sort key, try to break the strategy with 3-5 elements, and clarify the problem variant
You see "maximize" or "minimize" and something clicks. Greedy. Local optimum at each step, done in O(n log n). Start coding.
The interviewer watches. You pass two examples. The third breaks. You stare at it for ten seconds and say "let me trace through this again."
That's not bad luck. These are greedy algorithm mistakes that repeat across candidates, and every one of them is completely predictable.
"It Seems Greedy" Is Not a Proof
The coin change problem with coins [1, 3, 4] and target 6 illustrates this faster than anything else.
Greedy picks the largest coin first: 4 + 1 + 1 = 3 coins. The correct answer is 3 + 3 = 2 coins. You just confidently did more work than a child with a piggy bank.
def coins_greedy(coins, amount): coins.sort(reverse=True) count = 0 for coin in coins: while amount >= coin: amount -= coin count += 1 return count coins_greedy([1, 3, 4], 6) # returns 3. optimal is 2.
Greedy fails whenever a locally optimal choice consumes capacity that blocks a better global combination. Picking 4 leaves you with 2, which forces two 1s. Picking 3 twice costs less. The algorithm has no way to undo that first choice, because it's greedy, and greedy algorithms have the emotional flexibility of a golden retriever: they love whatever's in front of them right now.
This trips people up because US coin denominations are canonical, meaning greedy-by-largest actually works for [1, 5, 10, 25]. That's a coincidence of denomination structure, not a property of the greedy strategy. Switch to arbitrary denominations and the proof evaporates.
Before you code, spend 60 seconds trying to break your strategy with 3 to 5 elements. If you can't find a counterexample, sketch the exchange argument: if you swap the greedy choice for any other choice at each step, does the global solution get worse or stay the same? If swapping a non-greedy choice can never improve the result, the algorithm is correct. That reasoning, not "it passed my examples," is what the interviewer wants to hear.
For coin change with arbitrary denominations, no such exchange argument holds. That's why it needs dynamic programming.
The Wrong Sort Key Destroys Everything
Most greedy algorithms reduce to "sort by X, then sweep." The sort key is where candidates most often go wrong. It's the one decision that looks obvious, feels obvious, and very quietly produces wrong answers on a third of inputs.
Interval scheduling: start time vs. end time. The problem "select the maximum number of non-overlapping intervals" requires sorting by end time and picking the earliest-finishing interval that doesn't overlap the last selected. The exchange argument is clean: swap in an interval that finishes later and you block more future intervals, never gaining. Sorting by start time feels just as logical, but start time tells you nothing about how much future space an interval consumes. Finish time does.
LeetCode 179, Largest Number. Given [3, 30, 34, 5, 9], arrange to form the largest possible number.
First instinct: sort descending by numeric value. Try [3, 30]. Descending sort gives 30, 3, producing "303". But 3, 30 produces "330". Numeric sort is wrong.
The correct comparator: for two strings a and b, place a before b if a + b > b + a.
from functools import cmp_to_key def largest_number(nums): strs = list(map(str, nums)) strs.sort(key=cmp_to_key(lambda a, b: 1 if a + b > b + a else -1), reverse=True) result = ''.join(strs) return '0' if result[0] == '0' else result
The mistake is reaching for an obvious numeric sort without first constructing a counterexample. Fix: for any greedy sort, immediately test the "nearly equal" case. Two elements that score similarly on the naive metric but differ on the right one is almost always where wrong sort keys fail.
Variant Blindness: One Word Changes the Algorithm
The most reliable way to apply greedy incorrectly is to solve a different version of the problem than the one you were given. This is impressive, in a way. You've mastered a solution. Just not for this problem.
Fractional vs. 0/1 knapsack. Fractional knapsack: greedy by value-to-weight ratio, O(n log n), provably optimal. 0/1 knapsack: greedy by ratio fails, DP required, O(nW). The word "fractional" is doing all the work.
Here's the canonical counterexample for 0/1 knapsack with capacity 50:
| Item | Weight | Value | Ratio |
|---|---|---|---|
| A | 10 | 60 | 6.0 |
| B | 20 | 100 | 5.0 |
| C | 30 | 120 | 4.0 |
Greedy by ratio: take A (60), then B (100), total = 160. Optimal: B + C (weight 50, value 220). The greedy algorithm chose confidently and left 60 value on the table.
Why does fractional knapsack escape this? You can take a fraction of item C to fill the remaining 20 units. You can always patch the gap. In 0/1 knapsack you can't. The last unit of capacity might only be fillable by skipping an earlier item.
Weighted vs. unweighted activity selection. The earliest-finish-time greedy produces the maximum number of non-overlapping activities when all activities have equal value. Add different profits and the proof breaks. A high-profit activity that finishes late might be worth skipping earlier-finishing ones. That requires DP.
Before picking an algorithm, ask: "Do items have equal value, or different values?" and "Can items be divided?" Those two questions narrow you to the right approach.
See also when greedy fails for a full breakdown of the structural conditions.
The Two-Tracker Pattern You Keep Solving the Hard Way
Gas Station (LeetCode 134) is a greedy problem most engineers first solve in O(n²): try each starting station, simulate the full circle, move on. It works. It also times out. You've essentially written a polite brute-force and called it an algorithm.
The O(n) solution has a non-obvious invariant.
If you start at station start and run out of gas at station i, no station between start and i can be a valid starting point.
Proof: you reached each intermediate station with non-negative gas while starting from start. Starting at any of those stations means beginning with strictly less gas than you had when you passed through them. You'd fail earlier, not later.
That observation reduces the search space from O(n) candidates to one:
def can_complete_circuit(gas, cost): total_tank = 0 # global feasibility current_tank = 0 # local progress since last restart start = 0 for i in range(len(gas)): diff = gas[i] - cost[i] total_tank += diff current_tank += diff if current_tank < 0: start = i + 1 current_tank = 0 return start if total_tank >= 0 else -1
Two variables, one pass. total_tank answers "does a solution exist?" current_tank answers "where should we restart?" The valid starting point is always the station immediately after the minimum prefix sum of gas[i] - cost[i]. The algorithm finds that minimum implicitly.
The pattern generalizes. Many greedy problems on circular or reset-based structures need two trackers: one for global feasibility, one for local progress. If you see O(n²) in a greedy problem, look for the invariant that lets you skip failed segments.
Testing Easy Inputs Is How Greedy Fools You
Greedy solutions often pass small, well-shaped inputs even when they're wrong. The failure lives in adversarial cases. This is the part where you say "but it passed both examples!" and the interviewer nods in a way that says nothing good.
Longest Increasing Subsequence shows this clearly. Naive greedy: start with the smallest element, extend whenever you find something larger. Input: [10, 9, 2, 5, 3, 7, 101, 18].
Greedy starting at 10: gets [10, 101], length 2. Optimal: [2, 5, 7, 101], length 4. You left half the sequence on the floor because you committed too early to a bad element.
The greedy choice of "extend from whatever I see first" fails because an element that looks good now (10 or 9) cuts off a longer chain starting lower. See the greedy choice property for why LIS doesn't satisfy the structural conditions.
For any greedy you write, test three adversarial inputs before committing:
- All elements identical (exposes tie-breaking bugs)
- Elements in reversed expected order (exposes wrong sort direction)
- One element that looks optimal but creates a dead end
If your greedy survives all three, you have real confidence. If any breaks it, you caught the bug before writing 20 lines.
One edge case that keeps biting: the boundary condition in interval overlap. Is the condition start >= prev_end or start > prev_end? Intervals [1, 2] and [2, 3]: do they overlap? Your answer changes based on whether endpoints are inclusive or exclusive. Clarify this before you code.
Run This Diagnostic to Catch Greedy Algorithm Mistakes Before You Code
Before writing any greedy code, answer these:
- Name the choice. What exactly are you selecting greedily at each step? If you can't state it in one sentence, the algorithm isn't clear yet.
- Identify the sort key. What metric are you sorting by? Does the exchange argument hold? Test the "nearly equal" case.
- Try to break it. 3 to 5 elements. Can you construct a counterexample in under a minute? If yes, that's faster than finding out after 20 lines.
- Clarify the variant. Items divisible? Activities with values? Circular structure? These change everything.
- Edge cases. Empty input, single element, all elements identical.
If you can answer those questions and fail to find a counterexample, you're on solid ground. If you can't answer question 2 or survive the adversarial inputs in question 3, greedy isn't proven. Default to DP while you think.
Practicing this diagnostic out loud is harder than it looks on paper. That's one reason the gap between home practice and interviews is so wide. SpaceComplexity gives you voice-based mock interviews where the rubric includes your pre-coding validation, not just whether your final code runs.