Stage 1 · Code
Dynamic Programming & Greedy
Greedy Algorithms
When making the locally optimal choice at every step leads to the globally optimal solution — and how to tell if it will.
The Greedy Mindset
A greedy algorithm builds a solution step by step. At each step it picks the option that looks best right now — the 'local optimum' — hoping this chain of locally optimal choices will lead to a global optimum. No backtracking, no considering future consequences.
A problem is solvable with greedy if and only if a globally optimal solution can be reached by making a series of locally optimal (greedy) choices. This is the 'greedy choice property'. If it holds, greedy is O(n log n) or O(n). If it doesn't, you probably need DP.
Think of greedy like hiking a ridge line: at each fork, take the path that climbs highest immediately. If the ridge is shaped right, you'll reach the true summit. But if there's a valley before a higher peak, you'll get stuck on a local maximum — and that's when you needed DP or BFS instead.
When Greedy Works (vs. When It Doesn't)
Greedy works when the problem has two properties:
- Greedy Choice Property: a global optimum can be reached by a local optimum. Example: in Jump Game, the best reachable index from position i is the one that lets you jump farthest — you never need to 'save' a good jump for later.
- Optimal Substructure: an optimal solution to the whole problem contains optimal solutions to subproblems. Same as DP, but greedy chooses one subproblem instead of exploring all.
Classic cases where greedy works:
- Interval scheduling (earliest finish time → most intervals).
- Minimum spanning tree (Kruskal's, Prim's: pick cheapest edge that doesn't create a cycle).
- Huffman coding (merge two smallest frequencies).
- Coin change (with canonical coin systems like USD — but fails for [1,3,4] to make 6).
Greedy fails when a local choice precludes a better global solution. Classic example: coin change with denominations [1,3,4] and target 6. Greedy picks 4+1+1 = 3 coins. Optimal is 3+3 = 2 coins. Always test edge cases before committing to greedy!
Proof Strategies
During an interview you won't write a formal proof, but you should argue why greedy works. Two common proof techniques:
- Exchange argument: take an optimal solution and show you can transform it into your greedy solution without making it worse. This proves greedy is at least as good as optimal.
- Stay-ahead lemma: show that after k steps, the greedy solution is at least as far along as any optimal solution. Used for Jump Game, interval scheduling.
Practice Problems
Key Points
- Greedy is the fastest approach (O(n) or O(n log n)) but only works on problems with the greedy choice property.
- Test edge cases: can a small local loss enable a larger global gain? If yes, greedy fails — use DP.
- Interval problems almost always use greedy with 'earliest finish time' sorting.
- Jump Game problems use 'farthest reachable' — a tracking variable, not a decision tree.
- Exchange arguments are your interview tool for justifying greedy. Practice explaining them concisely.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.