Greedy Algorithms

Make the locally optimal choice at each step and never look back. When the greedy-choice property holds, it is both simple and provably optimal.

Key ideas

  • —Greedy works only when a local optimum is guaranteed to extend to a global one.
  • —You usually need to prove the greedy choice is safe — an exchange argument is the standard tool.
  • —When greedy fails, the problem almost always wants dynamic programming instead.

When greedy is correct

A greedy algorithm commits to the best-looking choice now and assumes it will not regret it. That only yields a correct answer when the problem has the greedy-choice property and optimal substructure. Best Time to Buy and Sell Stock works greedily because tracking the running minimum can never hurt a later sale; many superficially similar problems do not, which is why proof matters.

Reach, not position

A recurring greedy trick is to track the farthest reachable point rather than every path. Jump Game asks only whether the end is reachable, so you extend a running reach and succeed if it ever covers the last index. This single-pass view replaces an exponential search over jump sequences.

Practice this

Sources

← All lessonsNext: Heap / Priority Queue →