Greedy Algorithms Explained: Making Locally Optimal Choices

How Greedy Algorithms Work

A greedy algorithm follows a simple pattern. At each step, it evaluates the available choices, selects the one that appears best according to some criterion, and commits to that choice permanently. It never reconsiders or backtracks. This one-pass, no-regrets approach makes greedy algorithms efficient, often running in O(n log n) or O(n) time, far faster than algorithms that explore multiple possibilities.

The critical question is: when does being greedy produce the right answer? A greedy algorithm works correctly when the problem exhibits two properties. The greedy-choice property means that a locally optimal choice is always part of some globally optimal solution. The optimal substructure means that an optimal solution to the problem contains optimal solutions to its subproblems. When both properties hold, making the best local choice at every step leads to the best overall outcome.

Proving that a greedy algorithm is correct requires demonstrating these properties, typically through a "greedy stays ahead" argument (showing the greedy solution is at least as good as any other at every step) or an "exchange argument" (showing that any non-greedy choice can be replaced with a greedy one without worsening the result). These proofs can be subtle, and intuition alone is often misleading.

Classic Greedy Algorithms

Activity Selection

Given a set of activities with start and finish times, select the maximum number of non-overlapping activities. The greedy strategy sorts activities by finish time and always selects the activity that finishes earliest among those compatible with previously selected activities. This works because choosing the earliest-finishing activity leaves the most room for subsequent activities. The algorithm runs in O(n log n) time due to sorting, with the selection step taking O(n). This problem models real-world scheduling scenarios like booking conference rooms, scheduling television programs, and planning machine jobs.

Huffman Coding

Huffman coding creates an optimal prefix-free binary code for data compression. Characters that appear frequently receive shorter codes, while rare characters receive longer codes, minimizing the total number of bits. The algorithm builds a binary tree bottom-up: it starts with each character as a separate node weighted by its frequency, repeatedly merges the two lowest-frequency nodes into a new parent node, and continues until a single tree remains. The path from root to each leaf defines that character's binary code.

Huffman coding is provably optimal among prefix-free codes and is used as a component in many compression formats, including DEFLATE (used in ZIP files and PNG images), JPEG, and MP3. The algorithm runs in O(n log n) time using a priority queue.

Dijkstra Shortest Path

Dijkstra algorithm for finding shortest paths in graphs with non-negative weights is fundamentally a greedy algorithm. At each step, it selects the unvisited vertex with the smallest known distance and processes its neighbors. The greedy choice is guaranteed to be correct because, with non-negative weights, no future path through other vertices can produce a shorter distance to the selected vertex. This greedy property breaks down with negative weights, which is why Dijkstra algorithm requires non-negative edge weights.

Kruskal and Prim MST Algorithms

Both algorithms for finding minimum spanning trees use greedy strategies. Kruskal algorithm greedily selects the cheapest edge that does not create a cycle. Prim algorithm greedily selects the cheapest edge connecting the growing tree to an outside vertex. Both produce optimal MSTs because the "cut property" of MSTs guarantees that the lightest edge crossing any cut is part of some MST.

When Greedy Fails

Many optimization problems tempt greedy approaches but do not satisfy the greedy-choice property. The 0/1 knapsack problem, where items cannot be divided, is a classic example. Greedily selecting items with the highest value-to-weight ratio can miss better solutions. Consider a knapsack with capacity 10: item A weighs 6 and is worth 8, item B weighs 5 and is worth 5, item C weighs 5 and is worth 5. The greedy approach selects A (best ratio of 1.33) for a total value of 8, but selecting B and C together yields 10. The knapsack problem requires dynamic programming for an optimal solution.

The coin change problem also illustrates greedy limitations. With standard US coins (25, 10, 5, 1 cents), greedily choosing the largest coin that fits always produces the fewest coins. But with a non-standard set like {1, 3, 4} cents, making change for 6 cents greedily gives 4+1+1 (3 coins), while the optimal solution is 3+3 (2 coins). The greedy approach works for US coins only because of their specific mathematical properties.

The traveling salesman problem, graph coloring, and many other NP-hard problems cannot be solved optimally by greedy algorithms. Greedy heuristics for these problems can produce quick but suboptimal solutions, useful when exact solutions are too expensive but guarantees are not required.

Fractional vs. Discrete Problems

An interesting distinction is that greedy algorithms often work on continuous or fractional versions of problems where they fail on discrete versions. The fractional knapsack problem, where items can be divided into fractions, is optimally solved by greedily selecting items with the highest value-to-weight ratio and taking fractions of items when necessary. The discrete 0/1 version, where items must be taken whole or not at all, requires dynamic programming.

This pattern suggests a useful heuristic: if a problem allows fractional or continuous choices, a greedy approach is more likely to work. If choices are discrete and indivisible, greedy approaches should be validated carefully before relying on them.

Greedy vs. Dynamic Programming

Greedy algorithms and dynamic programming both use optimal substructure, but they differ in how they make decisions. Greedy algorithms make one irrevocable choice at each step, committing before seeing the consequences. Dynamic programming considers all possible choices at each step, comparing their outcomes before deciding. Greedy algorithms are faster when they work (typically O(n log n) vs. polynomial DP tables), but DP applies to a broader class of problems.

A useful diagnostic: if a greedy choice can be proven correct by an exchange argument, use greedy. If the optimal choice at each step depends on solutions to subproblems you have not computed yet, use dynamic programming. When in doubt, start with a greedy solution, test it against known optimal solutions, and switch to DP if the greedy approach fails.