Greedy
When is the locally best choice provably safe?
Forty hours for one report
A treasury team sets money aside every night to cover the next day's merchant payouts. To size it they want one number per merchant: the stretch of consecutive minutes last month in which the most money came in, net of refunds.
A month is 43,200 minutes. The direct version is a nested loop: for every start minute, walk forward, keep a running total, remember the best. That is about 933 million additions per merchant. Python needs over a minute for each, and 2,400 merchants are on the plan. Do the sum: the nightly job needs about 40 hours.
Stand at minute 9,000 and ask what you still need to know about everything before it. Take the best stretch that ends exactly at minute 8,999. If its total is positive, it is worth keeping: minute 9,000 added to the end of it gives a larger total than minute 9,000 alone. If its total is negative, it only lowers the total of any stretch that includes it, so every such stretch would do better without it.
Pause and predict You scan minute by minute, keeping the best stretch that ends at the current minute. Its total has dropped to -₹40. What do you do with it?
A choice you never have to undo
A greedy algorithm builds its answer one choice at a time and never goes back. That is why it is fast: usually one pass, no table, no recursion.
Every greedy algorithm also makes a claim: the choice that looks best right now is part of some best answer. For some problems that claim is true. For many it only looks true.
Two arguments keep that invariant, and you should be able to say one of them out loud for every greedy you write.
- Exchange. Take any optimal answer that differs from the greedy choice. Put the greedy choice in its place, and show that the answer is no worse. Then an optimal answer that agrees with the greedy choice exists.
- Stays ahead. Measure progress after each step, such as how far you can reach or how many pieces you have cut. Show by induction that the greedy algorithm is never behind any other strategy at any step.
Dropping the negative stretch in the opening example is an exchange argument: take any stretch that begins with a part whose total is negative, cut that part off, and the stretch's total goes up.
Hunt for a counterexample first
Before you look for a proof, spend a minute trying to break the rule with a tiny input: two or three elements, a zero, or a value that pulls the wrong way. That minute costs much less than writing a wrong solution. Here are four rules that sound reasonable. For each one, decide whether it holds before you see the answer.
The coin failure is worth remembering. Taking the 4 changed what was left to pay, and no later choice could make up for it. When one choice changes what the later choices are worth, the right tool is dynamic programming, which keeps every option open. A greedy algorithm works only when no choice ever needs to be undone.
Kadane: drop a negative prefix
Maximum Subarray is the treasury report as an array problem: find the block of consecutive elements with the largest sum. There are about n²/2 blocks. Kadane's algorithm looks at each index once and asks a smaller question: what is the best block that ends exactly at this index?
A block ending at i is either nums[i] alone, or nums[i] added to the end of a block ending at i - 1. The best block of the second kind uses the best block ending at i - 1. Call that block's sum cur.
The test looks at cur, the running sum. A negative element can still be worth crossing: in [3, -1, -1, 4] the best block is the whole array, with sum 5. Kadane is also the smallest dynamic programming solution there is, dp[i] = nums[i] + max(dp[i - 1], 0), stored in one variable. The greedy view explains why the max with 0 is there.
How to recognise it
Greedy problems are the hardest to recognise from the statement, and they need a proof more than any other pattern. A statement rarely says "greedy". What it usually gives you is a quantity that only moves in one direction, such as how far you can reach, a deadline, or the last position of a letter, and a choice that never needs revisiting once it is made.
Pause and predict Three houses in a row hold 3, 4 and 3, and you cannot rob two houses next to each other. If you rob the biggest house first, do you get the most money?
Problems that only look like it
- Choices that affect each other: making change with any set of coin values, or robbing houses where neighbours cannot both be robbed. That is dynamic programming.
- Ranges with start and end points: choosing meetings, merging ranges, shooting arrows at balloons. Those are greedy too, but most of the work is in choosing the sort order, so they are in intervals.
- Taking the best item again and again when the set of items changes after each take: the greedy needs a heap to find the best item quickly.
- "The smallest X that works": the check for one X is often a greedy, but the search over X is binary search.
Where it bites
Pause and predict Kadane's algorithm is written with cur and best both starting at 0. What does it return on [-5, -2, -8]?
- Trusting a greedy rule that only looks right. Largest coin first, longest jump first and most gas first all fail. Try a small input of two or three elements before you write code.
- Restarting Kadane on a negative element instead of on a negative running sum.
[3, -1, -1, 4]then answers 3 instead of 5. - Starting
bestat 0. When every element is negative, the answer must be the largest element, which is below 0. - Off by one at the end. Jump Game II never jumps from the last index, so
[0]needs 0 jumps. In Gas Station the new start isi + 1, one past the station whose leg ran the tank dry. - Forgetting the overall check. Gas Station returns a station only if the total gas covers the total cost.
- Not raising
loback to 0 in Valid Parenthesis String. Without it,*(would pass:logoes to -1 at the star and back to 0 at the "(", although that "(" is never closed.