A greedy algorithm makes the locally optimal choice at every step, committing to that choice permanently and never looking back. The hope is that a sequence of locally optimal decisions produces a globally optimal result. When this hope is justified, greedy algorithms are among the simplest and most efficient approaches available. When it is not justified, greedy algorithms produce wrong answers that look plausible.

Greedy vs Dynamic Programming

The critical difference between greedy and dynamic programming is commitment. A greedy algorithm picks one option at each step and moves on. A dynamic programming algorithm considers all options, solves subproblems for each, and combines results to find the true optimum. DP is exhaustive and always correct (for problems with optimal substructure and overlapping subproblems). Greedy is fast and elegant but only correct when a specific mathematical property holds.

Consider making change for 30 cents with coins {25, 10, 5, 1}. Greedy picks the largest coin that fits: 25 + 5 = two coins. DP would consider all combinations and confirm that two coins is optimal. For US coins, greedy happens to work. But swap the coin set to {1, 3, 4} and target 6: greedy picks 4 + 1 + 1 = three coins, while the optimal is 3 + 3 = two coins. Greedy failed because it committed to the 4-cent coin without considering that two 3-cent coins would be better.

When Greedy Works: Two Required Properties

A greedy algorithm is correct when the problem has both of these properties:

Greedy choice property - there exists an optimal solution that includes the greedy (locally optimal) choice. In other words, making the locally best decision at the first step does not prevent you from reaching a globally optimal solution.

Optimal substructure - after making the greedy choice, the remaining subproblem is a smaller instance of the same problem, and its optimal solution combines with the greedy choice to form an optimal solution to the original problem.

Both properties must hold. Optimal substructure alone is not enough - DP problems have optimal substructure too. The greedy choice property is what distinguishes greedy from DP: it says you do not need to explore all options because the locally best option is guaranteed to be part of some optimal solution.

The Exchange Argument

The exchange argument is the standard proof technique for greedy correctness. The idea is: assume you have some optimal solution that does NOT make the greedy choice at some step. Show that you can swap (exchange) the non-greedy choice for the greedy choice without making the solution worse. If every such swap preserves optimality, then there must exist an optimal solution that makes the greedy choice at every step - which is exactly the greedy algorithm's output.

Here is the structure of an exchange argument:

1. Assume an optimal solution O that differs from the greedy solution G at some step k
2. At step k, O chose option A while G chose option B (the greedy choice)
3. Construct a modified solution O' by swapping A for B
4. Show that O' is at least as good as O (no worse)
5. Conclude that the greedy choice at step k is safe

You do not need to write a formal proof in an interview, but you do need to articulate why the greedy choice at each step cannot hurt. The question to keep asking yourself is: "Can I prove that committing to this choice now never hurts?"

Common Patterns Where Greedy Works

Greedy algorithms tend to work on problems involving:

• Scheduling - selecting the maximum number of non-overlapping activities, minimizing lateness
• Graphs - minimum spanning trees (Kruskal, Prim), shortest paths (Dijkstra with non-negative weights)
• Compression - Huffman coding, where merging the two least-frequent symbols first is provably optimal
• Reachability - jump games, where tracking the farthest reachable position is greedy

The recurring theme is that these problems have a natural ordering (by end time, by weight, by frequency, by position) that makes the greedy choice obvious and provably safe.