Skip to interview prep
Apexed

47. When does a greedy algorithm give the optimal answer?

MediumGreedy algorithms

Technical
Show model answer

A greedy algorithm makes the locally best choice at each step without revisiting it. It is optimal when the problem has the greedy-choice property (some optimal solution starts with the greedy choice) and optimal substructure. Prove it with an exchange argument.

Examples that work: activity selection (earliest finish time), Huffman coding, Dijkstra, and Kruskal/Prim. Examples that fail: coin change with arbitrary denominations and 0/1 knapsack, which need dynamic programming.

When does a greedy algorithm give the optimal answer — Data structures & algorithms interview question — Apexed