Spot When Greedy Fails
Find counterexamples before trusting it.
Spot When Greedy Fails is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Greedy Is Tempting
Greedy is short, fast, and feels obvious, which is exactly why it can trap you. A clean idea is not the same as a correct one. ⚠️
The Coin Change Trap
With coins 1, 3, and 4, making 6 greedily picks 4 then needs two 1s, totaling three coins. The real best is two 3s.
What Went Wrong
The biggest coin was a local win that blocked the global best. Greedy could not undo it, so it missed the two-coin answer.
Find a Counterexample
Your fastest check is a tiny counterexample: a small input where greedy and the true optimum differ. One is enough to reject it.
0/1 Knapsack Again
Greedy by ratio fails for indivisible items: a dense tiny item can crowd out two items that together beat it. Splitting was the missing freedom.
When Choices Interact
If picking one item changes which others are still worth taking, greedy often breaks. Tangled dependencies point you toward DP.
Stress Test It
Write a slow brute force and a random generator, then compare both on thousands of small cases. A single mismatch exposes the flaw.
for _ in range(10000):
t = random_case()
assert greedy(t) == brute(t)The Exchange Test
To trust greedy, try to prove an exchange argument. If you cannot show the greedy pick fits some optimal answer, stay suspicious.
Greedy as a Subroutine
Even when it is not the whole answer, greedy can be a building block inside a larger DP or search. Use it where it is provably safe.
Read the Constraints
Small N often means you do not need greedy at all. Brute force or DP may pass, and they sidestep the correctness risk entirely.
A Habit That Saves Points
Before submitting a greedy guess, spend a minute hunting a counterexample. That tiny check prevents a painful wrong-answer verdict.
Quick Check
You suspect a greedy strategy might be wrong.
Recap
Greedy fails when a local win blocks the global best, as in some coin sets and 0/1 knapsack. Hunt counterexamples and stress test before you trust it. 🚀
Frequently asked questions
Is the “Spot When Greedy Fails” lesson free?
Yes — the full text of “Spot When Greedy Fails” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Spot When Greedy Fails”?
Find counterexamples before trusting it. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Spot When Greedy Fails” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- The Greedy Mindset
- Activity Selection by Earliest Finish
- Fractional Knapsack by Ratio
- Spot When Greedy Fails