Skip to content

Topic 15 of 20

Greedy

Make the locally best choice, and learn to prove it is globally optimal.

20 problems5 Easy12 Medium3 Hard

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

  1. 1

    Match the smallest sufficient cookie; the simplest exchange argument.

    Sort + GreedyReported at: Apple
  2. 2

    Prefer giving larger bills as change.

    Greedy SimulationReported at: AmazonAppleAtlassian
  3. 3

    Fractional-knapsack style: best value first.

    Sort + GreedyReported at: AmazonLinkedInJPMorgan Chase
  4. 4

    Place whenever it is legal; a greedy that is easy to justify.

    Greedy ScanReported at: MetaAmazonLinkedIn+1
  5. 5

    Sort and check consecutive triples.

  6. 6

    Kadane's algorithm; among the most-asked problems ever.

    Kadane's AlgorithmReported at: AmazonAppleMicrosoft+18
  7. 7

    Sum every positive difference.

    Greedy (Collect Every Gain)Reported at: AmazonMetaGoogle+5
  8. 8
    Jump GameMedium

    Track the furthest reachable index.

    Reachability (Jump Game)Reported at: AmazonMetaApple+5
  9. 9

    Greedy BFS levels for the minimum number of jumps.

    Reachability (BFS Levels)Reported at: AmazonAppleGoogle+5
  10. 10

    Reset the start when the running tank goes negative.

    Greedy with ResetReported at: AmazonMicrosoftApple+6
  11. 11

    Always extend from the smallest remaining card.

  12. 12

    Ignore bad triplets and combine the rest.

  13. 13

    Extend each partition to the last occurrence; asked often at Amazon.

    Greedy with Last OccurrenceReported at: AmazonGoogle
  14. 14

    Track the range of possible open counts.

    Greedy Range TrackingReported at: AmazonMetaGoogle+1
  15. 15

    A custom comparator (a+b vs b+a).

    Custom Sort GreedyReported at: MicrosoftMetaAmazon+6
  16. 16

    Sort tall-first, then insert by index.

    Sort + Greedy InsertionReported at: Meta
  17. 17

    Sorting by cost difference is the exchange argument in action.

    Sort by DifferenceReported at: MetaBloomberg
  18. 18
    CandyHard

    Left pass then right pass to satisfy both neighbours.

    Two-pass GreedyReported at: Amazon
  19. 19

    Retroactively refuel at the best station passed.

  20. 20

    Extend the reachable sum range greedily.

    Greedy CoverageReported at: Amazon