When Greedy Fails: Greedy vs Optimal Solutions, Explained
- A greedy algorithm fails when the greedy choice property doesn't hold: a locally optimal pick can lock you out of the global best
- The coin change counterexample (denominations {1, 3, 4}, target 6) proves greedy is wrong with arbitrary denominations even when it works for US coins
- Two conditions guarantee greedy is optimal: greedy choice property (safe to commit without backtracking) and optimal substructure (subproblem is also greedily solvable)
- The exchange argument is the standard correctness proof: show that swapping the greedy choice into any optimal solution never makes things worse
- When greedy is correct it beats DP on complexity: activity selection O(n log n) vs O(n²), Dijkstra O((V+E) log V) vs Bellman-Ford O(VE)
- In interviews, spend 60–90 seconds trying to construct a counterexample before committing to greedy; if you can't break it, articulate the exchange argument
Greedy algorithms have a reputation problem. Some engineers over-trust them ("just pick the biggest each step, obviously"), get burned by a single counterexample in an interview, and look confused when the interviewer says "are you sure?" Others see the word "optimization" and immediately reach for DP, writing 50-line tables for problems that need five lines. Both are wrong. The truth is precise: greedy fails when the problem lacks a specific structure. When that structure is present, greedy is provably optimal and runs circles around any DP solution you'd write.
"Optimal" and "Greedy" Are Not Synonyms
"Optimal" means best possible: fewest coins, maximum profit, shortest path. It says nothing about the algorithm.
"Greedy" describes a strategy: make the locally best choice at each step and never revisit that decision. Like a golden retriever at a buffet. Confident, fast, and completely uninterested in the consequences.
A greedy algorithm reaches the global optimum only when the problem has a specific structure. Without that structure, it gives you an answer. Just not the best one.
Three outcomes are possible when you apply greedy to an optimization problem:
- Greedy is provably optimal (activity selection, Dijkstra on non-negative graphs, fractional knapsack)
- Greedy is a useful approximation but not optimal (many NP-hard problems)
- Greedy is outright wrong (coin change with arbitrary denominations, 0/1 knapsack)
The goal is to tell these apart before you code, not after the interviewer starts writing notes.
When a Greedy Algorithm Fails: The Coin Counterexample
Coin change is the canonical example. Given a set of denominations and a target amount, find the minimum number of coins.
With US coins {25, 10, 5, 1} and a target of 30 cents, greedy works exactly as expected:
def greedy_coins(coins, amount): coins = sorted(coins, reverse=True) count = 0 for coin in coins: while amount >= coin: amount -= coin count += 1 return count greedy_coins([25, 10, 5, 1], 30) # 2 coins: 25 + 5
Now change the denominations to {1, 3, 4} and target 6.
Greedy picks 4 (the largest that fits), then 1, then 1. Three coins: {4, 1, 1}.
The optimal answer is two coins: {3, 3}.
Greedy got the wrong answer. Not close. Not off by rounding. Structurally wrong, and it has no mechanism to recover because it committed to that first pick and moved on.
The greedy approach: passes all your test cases, fails the moment someone tries coins = [1, 3, 4] and amount = 6.
This is not a contrived trick. It's a direct consequence of the problem structure. The choice at step one (picking 4) locked us into a worse path. The denominational gap between 3 and 4 means that locally picking the biggest coin forces us to overshoot and backfill with 1s. Greedy has no way to notice this happening.
The Two Properties That Make Greedy Safe
Two conditions, when both hold, guarantee a greedy algorithm reaches the global optimum.
Greedy choice property: a locally optimal choice can always be extended into a globally optimal solution. You will never need to undo a greedy decision to reach the best outcome. The problem is structured so that grabbing the best option now never forecloses the best result later.
Optimal substructure: once you make a greedy choice, the remaining subproblem also has an optimal solution achievable through the same strategy.
Coin change with arbitrary denominations fails the first property. Picking the biggest coin first is not always safe, because the gaps between denominations mean a locally large pick can leave you unable to reach the target efficiently.
US coins satisfy the property due to their specific divisibility structure. That's a coincidence of denomination design, not a general rule about coin problems.
When Greedy Is the Optimal Algorithm
The activity selection problem is where greedy provably wins.
You have a list of events with start and finish times. You want to schedule as many non-overlapping events as possible in a single room. The greedy strategy: sort by finish time, and always pick the earliest-finishing event that does not conflict with the last one selected.
def activity_selection(activities): activities.sort(key=lambda a: a[1]) selected = [activities[0]] for start, finish in activities[1:]: if start >= selected[-1][1]: selected.append((start, finish)) return selected
Why is this optimal? The proof uses an exchange argument. Take any optimal solution that does not start with the earliest-finishing event. Swap in the earliest-finishing event instead. The number of scheduled activities does not decrease, because the earliest finisher leaves at least as much room for future events as whatever it replaced. Any optimal solution can be transformed into one that starts with the greedy choice, without losing anything.
The exchange argument is the standard proof technique for greedy correctness. If you can show that swapping a greedy choice into an optimal solution never makes things worse, the greedy choice property holds, and you are done.
Dijkstra's algorithm follows the same logic. It greedily relaxes the closest unvisited node at each step. Non-negative edge weights guarantee that a node's shortest distance is finalized the moment it is popped from the priority queue. No future path can circle back and improve it. That's exactly why Dijkstra runs in O((V + E) log V) instead of the exponential cost of exploring all paths.
Greedy Is Almost Always Faster When It's Correct
When greedy is provably correct, it beats the DP alternative by a lot.
For coin change, DP runs in O(n x amount) time and O(amount) space, where n is the number of denominations. For a target of 10,000 with 10 denominations, that is 100,000 operations, plus a table you have to allocate. For coin systems where greedy works, the greedy approach sorts in O(n log n) and scans once. Constant space. Done.
| Problem | Greedy | DP |
|---|---|---|
| Coin change (US coins) | O(n) | O(n x amount) |
| Activity selection | O(n log n) | O(n²) |
| Dijkstra's shortest path | O((V+E) log V) | Bellman-Ford: O(VE) |
| Fractional knapsack | O(n log n) | n/a (greedy is exact) |
The speed gap is why proving greedy correctness is worth the effort. Confirm the greedy choice property holds, and you skip the DP table entirely.
How to Decide in an Interview
When you encounter an optimization problem, here is the reasoning sequence that actually works under pressure.
Step 1: Form a greedy hypothesis. Is there a natural "always pick the best at each step" strategy? For interval problems, "earliest finish time" is the common anchor. For problems with ratios, "highest value per unit" often works. State it out loud so the interviewer can follow your thinking.
Step 2: Try to break it. Spend 60 to 90 seconds constructing a small counterexample. For coin change with custom denominations: does the greedy choice at step one ever strand you? If you find one case where greedy fails, you are done with greedy. If you genuinely cannot construct a counterexample after real effort, that is evidence (not proof, but useful evidence) that greedy might be safe.
Step 3: Apply the two-property test. Ask whether the locally optimal choice is always safe to commit to. Can you sketch why picking the best option now can never require undoing later? If you can articulate that, you have a real argument for greedy. If you cannot, DP is the right move. This decision is not random.
Before you commit to the greedy choice, ask: can you name a counterexample? If you cannot, that is evidence, not proof.
For a deeper look at the signals that distinguish greedy from DP before you code, see the greedy vs dynamic programming guide. The greedy choice property post covers the formal one-test check in more detail.
Three Ways to Get Greedy Wrong
Applying greedy to 0/1 knapsack. The fractional knapsack (where you can take partial items) is greedy-optimal via the value-per-weight ratio. The 0/1 knapsack (take or leave each item whole) is not. The atomicity of items breaks the greedy choice property, because you cannot take 0.7 of an item to make up the difference. You need DP.
Confusing "works on examples" with "is correct." Greedy often produces the right answer on small, friendly examples even when it's provably wrong in general. The coin change counterexample requires {1, 3, 4} and target 6, not the typical {1, 5, 10, 25} and target 30. If you only test happy paths, you will convince yourself greedy works right up until the interview where it does not.
Skipping the justification. In an interview, saying "I will use greedy" without explaining why is a signal problem. Saying "greedy is safe here because picking X first never requires backtracking, by the exchange argument" tells the interviewer you understand the algorithm, not just the code pattern. See technical interview communication for how this reasoning lands in a real interview.
What Greedy Problems Actually Look Like
Problems that tend to be greedy-optimal share a pattern: the choice at each step can be made independently, and making the locally best choice consistently narrows toward the global best. There is no interaction between choices that would create regret.
Problems that require DP share a different pattern: choices interact across positions. The decision at step one changes the shape of the problem at step two in a way that greedy cannot see. The dynamic programming framework covers how to identify that structure before you commit to an approach.
Some interview problems that reward greedy:
- Jump Game I (LeetCode 55): track the farthest reachable index. O(n), no DP needed.
- Meeting Rooms II (LeetCode 253): sort by start time, use a min-heap of end times.
- Non-overlapping Intervals (LeetCode 435): sort by end time, always keep the earlier-finishing interval.
- Task Scheduler (LeetCode 621): frequency-based greedy, not DP.
If you want to practice explaining the greedy choice property under interview conditions, not just implementing it, SpaceComplexity runs voice-based mock interviews with rubric feedback across communication, problem-solving, and approach justification.