Greedy Overview & Exchange Argument

A greedy algorithm makes the best-looking choice at each step and never revisits it. When it works, it's usually the simplest and fastest solution, often a sort plus one pass. The hard part isn't the code but knowing that the local choice is safe. That's tricky, because greedy problems often look a lot like DP problems.

The idea#

Greedy works when a locally optimal choice leads to a globally optimal answer. The test is: if the current choice doesn't affect which future choices are available (or only leaves more of them), greedy works. If it does, you need DP to explore the options.

Three signs point to greedy:

1. Making the locally best choice at each step gives the global best.
2. You never need to undo or revisit an earlier decision.
3. There's often a sort first, then a single pass in that order.

If you can't convince yourself of these, or you find a counterexample, use DP.

How to spot it#

Ask these questions before choosing greedy over DP:

The usual shape#

Most greedy solutions share one shape: sort by the key that makes the next choice obvious, then make that choice in one pass. The sort costs $O(n \log n)$ and the pass costs $O(n)$.

sort items by the key that makes the best next choice obvious
state = starting value                 # last chosen end, count, total
for each item in sorted order:
    if item is compatible with state:  # the locally best move is safe
        take it and update state
    else:
        skip it, or start a new group
return the answer built from state

The code is the easy part. The real work is choosing the key and proving that the local choice is safe, which the next section covers.

Proving it: the exchange argument#

The standard proof asks: "if you sort and pick this way, can anything else be better?" Take any optimal answer that differs from the greedy one. Find the first place they differ and swap the optimal answer's choice for the greedy choice. If the result is still valid and no worse, you can repeat until the optimal answer is the greedy one, so greedy is optimal too.

With intervals, the swap often moves a choice to the earliest end. No interval ends earlier, so the moved choice misses nothing, and it leaves the most room on the number line for everything after it.

Two other proof styles come up often:

• Edges are extremes: in a sorted array, the smallest and largest values are guaranteed to be at the ends, which lets you argue that pairing them one way can't be beaten (see Sort, Then Place or Pair).
• Telescoping sums and bounds: split the target into pieces you can reason about one by one, or show the answer can't exceed a bound and then reach it (see Counting & Bound Arguments).

When DP was the first idea#

Sometimes DP is the first idea that comes to mind, and a DP solution even works, but it's too slow. A DP over "last index and some state" can time out where one pass over the input would do. Look for what matters to the answer and drop everything else. Wiggle Subsequence in the hints below is the classic case.

Maximum Number of Weeks (LC 1953) is another example: a heap simulation works, and a counting argument then replaces it with a closed form.

When greedy fails#

The opposite mistake is trusting greedy when a choice does close off options. These two are the classic cases.

• Coin change with arbitrary coins. With coins [1, 3, 4] and amount 6, "largest coin first" gives 4 + 1 + 1 (3 coins); 3 + 3 uses 2. Greedy is only safe for canonical systems such as [1, 5, 10, 25].
• 0/1 knapsack. Greedy by value per weight is optimal only when items can be split (fractional knapsack). With whole items, use DP.

Where other greedy patterns live#

Greedy shows up in other parts of the site too. These patterns have their own notes.

Pitfalls#

These mistakes cause the most wrong answers.

• Trusting a greedy rule because it passes the examples. Try to break it with a small counterexample first.
• Sorting by the wrong key. For interval problems, start vs end time decides whether the greedy is correct.
• Reaching for DP on a problem with an obvious one-pass greedy, then getting a time limit.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

• 1710. Maximum Units on a Truck
• 452. Minimum Number of Arrows to Burst Balloons
• 435. Non-overlapping Intervals
• 376. Wiggle Subsequence
• 53. Maximum Subarray
• 55. Jump Game

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Greedy works when the current choice doesn't restrict future choices.
• Sort first, then make the obvious choice in one pass.
• Prove it with an exchange argument: swapping in the greedy choice never hurts.
• When a choice removes options you might need, use DP.
• Test a greedy rule against a small counterexample before trusting it.