Free lesson · DSA Mastery - Interview Prep, End to End
Introduction to Greedy Algorithms
Introduction to Greedy Algorithms
A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now - the locally optimal move - and never reconsidering it. The gamble is that a sequence of locally optimal choices adds up to a globally optimal solution. When that gamble pays off, greedy algorithms are among the simplest and fastest tools you have: usually a sort followed by a single linear scan, no recursion stack, no memo table, no branching search. When it doesn't pay off, greedy quietly returns a wrong answer that looks plausible - which is exactly what makes this paradigm both powerful and dangerous.
This section is about developing the judgment to tell the two cases apart, and the techniques to implement greedy correctly once you've recognized it applies.
What "Greedy" Actually Means
Consider making change for 41 cents with US coins (25, 10, 5, 1). The greedy rule - "take the largest coin that fits, repeat" - gives 25 + 10 + 5 + 1, four coins, which happens to be optimal. The locally optimal choice (grab the biggest coin) led to the global optimum (fewest coins). But change the coin system to {1, 3, 4} and ask for 6: greedy takes 4 + 1 + 1 (three coins), while the optimum is 3 + 3 (two coins). Same rule, same kind of problem - and greedy fails on the second.
That contrast is the whole lesson of this section in miniature. Greedy is not a universal method; it is a method that works for problems with a particular structure, and the entire skill is recognizing whether your problem has that structure before you trust the greedy answer.
Important: The danger of greedy is not that it crashes or runs slowly when it's wrong - it's that it returns a confident, plausible-looking wrong answer. Dynamic programming that's wrong usually looks wrong. Greedy that's wrong looks right. Always justify why the greedy choice is safe before relying on it.
The Two Properties That Make Greedy Work
A problem is safely solvable by greedy when it has both of these:
Greedy choice property. A globally optimal solution can be reached by making the locally optimal choice at each step. In other words, the first greedy choice is part of some optimal solution - you never have to undo it. This is what lets you commit irrevocably and move on.
Optimal substructure. After making the greedy choice, what remains is a smaller instance of the same problem, and an optimal solution to the whole is the greedy choice plus an optimal solution to the remainder. (Dynamic programming also relies on optimal substructure - the difference is that greedy commits to one choice without exploring alternatives, while DP considers all of them.)
When both hold, greedy is correct and far cheaper than DP. When only optimal substructure holds but the greedy choice property fails, you usually need dynamic programming instead - which is why the {1,3,4} coin problem is a classic DP example, not a greedy one.
How to Prove a Greedy Algorithm Correct
There are two standard arguments, and recognizing which one fits is a real interview skill.
Tip: Exchange argument. Take any optimal solution and show that you can transform it, step by step, into the greedy solution without making it worse. If swapping the optimal solution's first choice for the greedy choice never increases cost (or never decreases value), then the greedy choice is safe. This is the most common proof for selection and scheduling problems - "sort, pick the best, and argue any other pick could be exchanged for ours."
Tip: Staying-ahead argument. Show that after each step, the greedy solution is at least as far along as any other solution by some measure. If greedy is never behind at any point, it can't lose at the end. This is the natural argument for the jump-game family - "after processing the first
ielements, greedy's reach is at least as large as anyone else's."
You don't always write these proofs out formally, but being able to sketch one is how you gain confidence that greedy is correct rather than just hoping it is.
The Recurring Shape of Greedy Solutions
Across this section you'll see the same skeleton again and again:
- Sort by the right key, then scan once. Most selection and scheduling greedy problems are "sort by deadline / by end time / by ratio / by height, then make a single pass committing to each best choice." Choosing the sort key is usually the entire insight - the scan that follows is mechanical.
- Track a running frontier or budget. The jump games track the farthest reachable index; gas station tracks a running tank; refueling tracks fuel with a heap of passed stations. The greedy choice is "extend the frontier as far as the current resources allow."
- Use a heap to always grab the current best. When the best available option changes as you scan, a priority queue surfaces it in O(log n) - the bridge between greedy and the heaps section (refueling stops, task scheduling, hiring workers).
- Commit with a counter or a stack. Parentheses and string greedy problems often scan left to right, maintaining a count of unmatched openers or a stack, committing a fix the moment an imbalance appears.
What This Section Covers
After this introduction, the section moves through:
- Selection greedy (Assign Cookies, Apple Redistribution into Boxes) - sort both sides, match greedily. The gentlest illustration of the exchange argument.
- The jump-game family (Jump Game, Jump Game II, Jump Game VII) - track the reachable frontier in a single sweep, the canonical staying-ahead argument, and where greedy decisively beats the obvious dynamic-programming solution.
- Parentheses and string greedy (Minimum Add to Make Parentheses Valid, Maximum Score From Removing Substrings) - scan with a counter or commit to the higher-value pattern first.
- Scheduling (Gas Station, Task Scheduler, Queue Reconstruction by Height, Avoid Flood in The City, Most Profit Assigning Work) - the heart of greedy, where sort-key choice and heap-assisted selection do the work.
- Array greedy (Maximum Swap, Maximum Matrix Sum) - single decisive swaps and sign-flip parity arguments.
- Hard greedy (Candy, Minimum Number of Refueling Stops, Minimum Cost to Hire K Workers, Set Intersection Size At Least Two) - two-pass sweeps, heap-driven retroactive choices, and ratio-plus-heap combinations that push the paradigm to its limit.
Note: Several scheduling and interval problems here will feel familiar from the Intervals section - earliest-finish selection, sweep-line counting, sort-by-start-or-end. That's not a coincidence: many interval problems are greedy problems, and the two sections share the same "sort by the right key, then commit" DNA. The difference in framing is that here we foreground the why - the exchange and staying-ahead arguments that justify the commitment.
The throughline for the entire section: greedy is a sort or a scan plus a commitment, and the hard part is never the code - it's proving the commitment is safe. Keep asking "why can't a different choice here do better?" If you can answer that with an exchange or staying-ahead argument, greedy is correct and you should use it. If you can't, reach for dynamic programming instead.
The next topic, Assign Cookies, starts the selection sub-group with the cleanest possible greedy: given children with greed factors and cookies with sizes, maximize how many children you can satisfy by sorting both and matching the smallest sufficient cookie to each child in turn. It is the textbook exchange-argument problem - every other matching can be rearranged into the greedy one without satisfying fewer children - and the ideal first concrete taste of the paradigm.