Greedy

Make the best-looking choice at each step and never undo it. Fast and short when it is correct, and wrong in quiet ways when it is not, so the proof matters as much as the code.

Overview

A greedy algorithm builds an answer one step at a time. At each step it takes the choice that looks best right now, by one fixed rule, and never goes back to change it.

That makes greedy code short and fast: usually one sort and one pass, O(n log n) time. The catch is that the rule is only sometimes right. Greedy problems test whether you can pick the right rule and explain why it cannot miss a better answer.

How a greedy algorithm runs

Most greedy solutions have the same shape: order the items by a key, walk through them once, and keep a small piece of state (the last end time, the farthest reach, the fuel left).

Key — In what order do I look at items? — by end time, earliest first
State — What do I remember between steps? — the end time of the last meeting kept
Fit test — When do I keep an item? — its start is at or after that end time
Answer — What do I return? — how many meetings were kept

Worked example: most activities in one room

Given activities with start and end times, keep as many as possible with no two overlapping. Here an activity that starts exactly when another ends does not overlap it. The greedy rule is earliest finish first: finishing early leaves the most room for what comes after.

starts at or after the end of the one before it. Every grey one starts before the last kept end.")

The trace sorts by end time, then walks once. Python's sort is stable, so B and C, which both end at 5, keep their input order.

| Step | Activity | Start, end | Last end before | Fits? | Kept so far | |---|---|---|---|---|---| | 1 | A | 0, 3 | none | yes | A | | 2 | B | 1, 5 | 3 | no: 1 [!TIP] > Before coding, try to break your key with a two- or three-item example. If you cannot, say so out loud and give the exchange argument below.

Why a greedy choice can be safe

A greedy algorithm is correct when two things hold.

Greedy choice — Some best answer starts with the greedy pick. — Some best schedule contains the activity that ends first.
Optimal substructure — After the pick, the rest is the same problem, smaller. — Keep the best schedule of what starts after that end.

There are two standard ways to argue the first property.

Exchange argument. Take any best answer that differs from the greedy one. Swap its first differing item for the greedy item and show the answer is still valid and no worse. Repeat until it matches the greedy answer.
Greedy stays ahead. Show that after every step, the greedy answer is at least as good as any other answer after the same number of steps. For intervals: the k-th interval greedy keeps ends no later than the k-th interval of any valid schedule.

When greedy fails

Greedy fails when taking the best item now uses up something a later, better combination needed. Two classic cases:

Coin change, coins 1, 3, 4 — largest coin that fits — amount 6 — 3 coins: 4, 1, 1 — 2 coins: 3, 3
0/1 knapsack, capacity 10 — best value per weight — weights 6, 5, 5 with values 30, 20, 20 — 30 (only the 6 fits) — 40 (both 5s)
Fractional knapsack, same items — best value per weight — take part of an item — 46: all of the 6 (30), then 4/5 of a 5 (16) — 46

The last two rows are the same items. Allowing fractions makes the greedy rule correct, because the leftover space can always be filled with the next-best ratio. With whole items only, you need dynamic programming (DP). For coins, the largest-first rule is optimal for US coins (1, 5, 10, 25, 100) but not for every coin set, so the general coin change problem is also DP.

Greedy or DP?

Choices — one per step, final — every option per state, best kept
Typical cost — O(n log n) for the sort, O(1) extra — O(states × choices) time and table space
Needs — greedy choice property and optimal substructure — optimal substructure and overlapping subproblems
Risk — wrong answer with no error — slower, but correct when the recurrence is right

Reach-style greedy: Jump Game

Not every greedy sorts. In Jump Game, each value is the longest jump allowed from that index, and the question is whether you can reach the last index. Walk left to right and keep reach, the farthest index reachable so far. If you ever stand past reach, you are stuck.

Here is the trace on [2, 3, 1, 1, 4], where the last index is 4.

0 — 2 — 0 — no — 2
1 — 3 — 2 — no — 4: reaches the end, return true

And here it is on [3, 2, 1, 0, 4], which gets stuck.

0 — 3 — 0 — no — 3
1 — 2 — 3 — no — 3
2 — 1 — 3 — no — 3
3 — 0 — 3 — no — 3
4 — 4 — 3 — yes: stuck, return false

Every path must land on index 3, and its value 0 goes nowhere. One pass, O(n) time, O(1) space.

What you will be able to do

Spot a greedy problem and name its key, state and fit test.
Break a wrong sort key with a two- or three-item counterexample.
Explain correctness with an exchange argument or a stays-ahead argument.
Tell when greedy fails (0/1 knapsack, arbitrary coins) and switch to DP.
Trace interval, reach and gas-station greedy solutions by hand.

When to use it

Pick the most non-overlapping intervals, or remove the fewest to make them non-overlapping
Fractional problems, where you can take part of an item
Reach problems: can I get to the end, and in how few jumps
Matching two sorted lists (cookies to children, workers to tasks)
Circular route problems where a running total decides the start (Gas Station)
Building a structure by cheapest-next-step rules: Huffman codes, minimum spanning trees
Coin change only for coin sets where largest-first is known to be optimal, such as US coins

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio