Topic 15 of 20
Greedy
Make the locally best choice, and learn to prove it is globally optimal.
The concept
A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, and never reconsiders. When it works, it is usually the simplest and fastest solution, often a sort followed by a single pass. The catch is that it only works when you can argue that the local choice never hurts the final answer.
The standard proof tool is the exchange argument: take any optimal solution that differs from the greedy one, swap in the greedy choice, and show it is no worse. In an interview you do not need a formal proof, but you should be able to explain why the greedy choice is safe. If you cannot, try a small counter-example, and if the greedy choice fails, the problem probably needs dynamic programming.
Common shapes include sorting by one key then scanning (assigning cookies, two-city scheduling), tracking the furthest reachable point (Jump Game), Kadane's running maximum subarray, and two-pass greedy where you satisfy constraints from the left and then from the right (Candy).
Patterns you will learn
Problems, in order
- 1Assign CookiesEasy
Match the smallest sufficient cookie; the simplest exchange argument.
Sort + GreedyReported at: Apple - 2Lemonade ChangeEasy
Prefer giving larger bills as change.
Greedy SimulationReported at: AmazonAppleAtlassian - 3
Fractional-knapsack style: best value first.
Sort + GreedyReported at: AmazonLinkedInJPMorgan Chase - 4
Place whenever it is legal; a greedy that is easy to justify.
Greedy ScanReported at: MetaAmazonLinkedIn+1 - 5
- 6Maximum SubarrayMedium
Kadane's algorithm; among the most-asked problems ever.
Kadane's AlgorithmReported at: AmazonAppleMicrosoft+18 - 7
Sum every positive difference.
Greedy (Collect Every Gain)Reported at: AmazonMetaGoogle+5 - 8Jump GameMedium
Track the furthest reachable index.
Reachability (Jump Game)Reported at: AmazonMetaApple+5 - 9Jump Game IIMedium
Greedy BFS levels for the minimum number of jumps.
Reachability (BFS Levels)Reported at: AmazonAppleGoogle+5 - 10Gas StationMedium
Reset the start when the running tank goes negative.
Greedy with ResetReported at: AmazonMicrosoftApple+6 - 11
- 12
Ignore bad triplets and combine the rest.
- 13Partition LabelsMedium
Extend each partition to the last occurrence; asked often at Amazon.
Greedy with Last OccurrenceReported at: AmazonGoogle - 14Valid Parenthesis StringMedium
Track the range of possible open counts.
Greedy Range TrackingReported at: AmazonMetaGoogle+1 - 15Largest NumberMedium
A custom comparator (a+b vs b+a).
Custom Sort GreedyReported at: MicrosoftMetaAmazon+6 - 16
Sort tall-first, then insert by index.
Sort + Greedy InsertionReported at: Meta - 17Two City SchedulingMedium
Sorting by cost difference is the exchange argument in action.
Sort by DifferenceReported at: MetaBloomberg - 18
- 19
Retroactively refuel at the best station passed.
- 20