Greedy Algorithms

8 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Greedy = take the best-looking choice now and never undo it. Fast (one sort + one pass), but only right with a proof.

   #1
2. ↯use it when

   One choice is always safe: furthest reach, restart after a failure, smallest card first. Can't say why in one line? Suspect DP.

   #2
3. { }template

   Sort by the key that makes the choice obvious → one loop → a few variables of state (reach, tank, lo/hi).

   #3
4. O( )cost

   Usually O(n) for the pass, O(n log n) with a sort. DP for the same problem is often O(n²); brute force is 2ⁿ.

   #4
5. !trap

   Coins {1, 3, 4}, amount 6: biggest-first pays 4+1+1 (3 coins), but 3+3 is 2. Test 2–3 tiny inputs before trusting greedy.

   #5
6. !trap

   Gas Station: the restart finds a candidate, but only total >= 0 says a start exists. Skip it and you return a wrong index.

   #6
7. ✦pro tip

   Prove it out loud: exchange (swap any best answer's choice for mine, no worse) or stays ahead (my reach is never behind).

   #7
8. ✦pro tip

   Unknown choices? Track a range. LC 678 keeps lo/hi open counts instead of trying all 3ᵏ meanings of the stars.

   #8

Shaky on a card? Open the chapter or flip its recall cards.