Greedy Algorithms
A greedy algorithm builds a solution piece by piece, always picking the option that looks best at the current moment without reconsidering past choices. Th...
What Is a Greedy Algorithm?
A greedy algorithm builds a solution piece by piece, always picking the option that looks best at the current moment without reconsidering past choices. The key insight is that a locally optimal choice at each step leads to a globally optimal solution — but only when the problem has two specific properties: the greedy-choice property and optimal substructure.
The greedy-choice property means you can safely make the locally best decision without worrying about future consequences. Optimal substructure means an optimal solution to the full problem contains optimal solutions to its sub-problems. When both conditions hold, greedy approaches are elegant and efficient, typically running in O(n log n) time due to an initial sort, with O(1) extra space.
A classic illustration is making change with the fewest coins. Given denominations 25, 10, 5, and 1, to make 41 cents you take the largest coin that fits at each step: one 25-cent coin (16 remaining), one 10-cent coin (6 remaining), one 5-cent coin (1 remaining), one 1-cent coin. Four coins total — optimal for standard denominations. However, with denominations 1, 3, and 4, a greedy approach for 6 cents picks 4 + 1 + 1 (three coins) while the true optimum is 3 + 3 (two coins). This illustrates that greedy does not universally work.
Interview tip: When asked whether a greedy approach is valid, immediately check for a counterexample with small inputs. If you can find one, dynamic programming is likely needed instead. Stating this trade-off clearly shows strong algorithmic maturity.
Correctness Proofs for Greedy Strategies
Proving that a greedy algorithm is correct requires more than intuition. The two standard proof techniques are exchange arguments and induction. An exchange argument shows that any solution different from the greedy one can be transformed into the greedy solution without making things worse, thereby proving the greedy solution is at least as good as any alternative.
Suppose you have a scheduling problem where jobs are sorted by deadline and you greedily assign each job to the latest available slot before its deadline. An exchange argument would take any optimal schedule that differs from the greedy schedule, find the first position of disagreement, swap the jobs, and show the swap does not increase lateness. Repeating this process transforms the optimal into the greedy schedule, proving correctness.
Induction is the second technique. Base case: a greedy choice for a single element is trivially correct. Inductive step: assume greedy works for k elements; show that adding the (k+1)-th element using the greedy rule still yields an optimal result. The inductive hypothesis carries the proof forward.
Understanding these proof strategies is important in practice because they tell you exactly which structural property the greedy rule is exploiting. When you cannot construct either proof, that signals the problem lacks the greedy-choice property and you should look at dynamic programming.
Interview tip: Even if you are not asked to formally prove correctness, mentioning that you would validate via an exchange argument signals to interviewers that you understand why greedy works, not just that it works.
Time and Space Complexity Analysis
Greedy algorithms earn their popularity partly from their efficiency. Most greedy solutions follow a two-phase pattern: sort the input, then make a single linear pass. Sorting costs O(n log n) and the pass costs O(n), so the overall time complexity is O(n log n). Space complexity is typically O(1) auxiliary if you sort in place, or O(n) if a copy is needed.
Compare this to dynamic programming, which often requires an O(n^2) table and corresponding time. For large inputs where n might be millions, the difference between O(n log n) and O(n^2) is enormous. This is why greedy algorithms are preferred when they are provably correct — they scale far better.
Some greedy algorithms use priority queues (heaps) to repeatedly extract the minimum or maximum element efficiently. Each heap operation costs O(log n), and if you perform n such operations the total is O(n log n) as well. Huffman coding for data compression is a famous example: build a min-heap of character frequencies, then repeatedly extract the two smallest and merge them.
A worked example: given n tasks each taking one unit of time and a profit if completed before a deadline, sort tasks by profit descending, then greedily assign each task to the latest free slot before its deadline using a boolean array. This runs in O(n^2) in the naive implementation but O(n log n) with a disjoint-set structure.
Interview tip: Always state time and space complexity unprompted. Saying "this greedy solution is O(n log n) time and O(1) space" immediately demonstrates that you think about resource usage, which is critical in systems with tight performance budgets.