A greedy algorithm builds a solution one step at a time, and at each step it commits to the choice that looks best right now, without ever revisiting or undoing a previous choice. There is no backtracking, no “try every option and compare” — just a single forward pass that keeps a small amount of state (a running best, a farthest reach, a count).
The pattern earns its own section because an enormous family of “minimum steps”, “maximum number of X”, “can you reach the end”, and “is this arrangement possible” problems become a 10-line loop once you identify the right local rule. The hard part is not the code; it is proving the local rule is safe.
Before writing any greedy code, ask yourself:
Can I prove that the locally-best choice at this step is part of SOME optimal solution?
Most “obvious” greedy rules fail this test. For example, “to make change,
always pick the largest coin that fits” works for US coins (1, 5, 10, 25)
but fails for denominations like {1, 3, 4} with target 6 (greedy picks
4+1+1 = 3 coins; optimal is 3+3 = 2 coins). That problem (LC 322, Coin
Change) belongs to the 1-D DP chapter precisely because no local rule is
safe for arbitrary denominations.
Reach for Greedy when the problem statement or input shows any of these:
| Signal | Example phrasing |
|---|---|
| Max number of X you can do | “maximum number of meetings you can attend”, “assign cookies” |
| Minimum steps / cost | “minimum number of jumps to reach the end”, “minimum refuels” |
| Reachability | “can you reach the last index”, “gas station circuit” |
| Subarray sum / max | “maximum sum of a contiguous subarray” (Kadane) |
| Locally-best choice works | “form straights from a hand of cards”, “container with most water” |
| Sorting + one pass | “merge intervals”, “non-overlapping intervals” — see also Pattern 13 |
The tell-tale sign: the brute force is exponential (try every subset / sequence), the DP formulation exists but feels heavy, and you suspect a single pass with one rule might work. Confirm the rule with an exchange argument or an invariant, then code it.
Almost every greedy solution in this section has this shape:
function greedy(input):
(optional) sort input by the right key
initialise a running best (running sum, farthest reach, count, ...)
for each element x in input:
update the running best using x
if a local choice must be made now:
commit to it (do NOT keep alternatives)
if the running state becomes invalid:
reset it (or restart from x)
return the accumulated answer
Two details matter more than the rest:
A few classic counterexamples to keep you honest:
The diagnostic test: try to construct a small input where the obvious local rule gives a worse answer than a different first move. If you can, greedy is out (or you have the wrong rule).
| # | LC | Problem | Difficulty | One-line teaser |
|---|---|---|---|---|
| 73 | 53 | Maximum Subarray | Medium | Kadane: a negative prefix never helps, so reset the running sum to 0. |
| 74 | 55 | Jump Game | Medium | Track the farthest reachable index; if you reach index n-1, win. |
| 75 | 45 | Jump Game II | Medium | Greedy BFS-like level expansion: count jumps, not paths. |
| 76 | 134 | Gas Station | Medium | Total surplus >= 0 ⇒ a circuit exists; one-pass restart finds the start. |
| 77 | 846 | Hand of Straights | Medium | Sort, count, then greedily consume each group from its smallest card. |
| 78 | 11 | Container Greedy | Medium | Same two-pointer move, but the win is the exchange argument that the shorter line is safe to drop. |
Work them in that order. The first three warm you up on the “running invariant” flavour of greedy. Gas Station is the classic “total + one-pass restart” insight. Hand of Straights adds sorting and a frequency map. Container Greedy closes the section by reframing a Two-Pointer problem as a greedy choice with a formal proof.
long for the running variable and cast back at the end.totalGas >= totalCost. Skip that check and you will return a
bogus start index on impossible inputs.Five questions ramping from recall to design. Try each before revealing.
Q1 (recall). In one sentence, what is the core question you must answer before trusting a greedy solution?
Q2 (pattern recognition). New problem: “given n meetings each with a start and end time, return the maximum number of non-overlapping meetings one person can attend.” Which greedy rule is provably optimal?
Q3 (pattern recognition). New problem: “make the amount 6 using the fewest coins from denominations {1, 3, 4}.” Is greedy safe here?
Q4 (apply). Run a Kadane-style greedy on nums = [-1, 2, 3, -1, 2]. What is the running sum right after the last element (2), and what is the final best?
Q5 (design). Sketch (in words, not code) a greedy solution for “assign cookies to children” (LC 455): each child has a greed factor g[i] (minimum cookie size to be content), each cookie a size s[j]; a child is content if given a cookie with s[j] >= g[i]. Maximize the number of content children.