32

Greedy Algorithms

Make the best-looking move now, never undo it, and prove it can't hurt.

intermediate~60 min5 simulations8 problems

▶ guided lesson⚡ 1-minute summary↻ 13 recall cards

before this: Big-O · Sorting

01 · why it exists

Why this exists, and the weight it carries

since1956–1971

The greedy method

Joseph Kruskal; Richard Rado; David Gale; Jack Edmonds

Greedy rules were in use before anyone could say when they work. Kruskal's 1956 minimum spanning tree adds the cheapest safe edge, again and again. Rado (1957), Gale (1968) and Edmonds (1971) found the clean answer for one big family of problems: "take the best remaining item that still fits" is optimal for every choice of weights exactly when the structure is a matroid. Edmonds' paper "Matroids and the greedy algorithm" is the classic reference. For everyday interview problems, you prove each greedy rule by hand instead: exchange argument or stays ahead.

the problem it solvedKnowing in advance when "always take the best remaining item" is guaranteed to be optimal, instead of hoping.

its jobs today

  • Compression: Huffman coding merges the two rarest symbols first; DEFLATE (gzip, PNG) is built on it.
  • Networks and maps: Kruskal's and Prim's spanning trees and Dijkstra's shortest paths are greedy algorithms.
  • Schedulers: shortest-job-first and earliest-deadline-first pick the next task by one simple rule.

the weight it carries

Illustrative: put 1 lakh (10⁵) jobs in the best order. Trying every order means 10⁵! orders, which is hopeless. Greedy sorts once, about 10⁵ × log₂ 10⁵ ≈ 10⁵ × 17 = 1.7 million comparisons, then makes one pass.

without it

Many scheduling and selection problems would need DP or brute force: O(n²) or worse, where one sort and one pass would do.

when · why · how

when
A choice exists that is always safe, whatever comes later, and you can say why in one line.
why
One sort + one pass: O(n log n), instead of DP's O(n²) or brute force's 2ⁿ. The price: it is simply wrong without a proof.
how
Sort with Arrays.sort (or keep a PriorityQueue / TreeMap when the best choice changes as you go), then one loop with a few variables of state.

02 · plain english

The idea in 30 seconds

A greedy algorithm builds the answer one step at a time. Each step takes the choice that looks best right now, and never undoes it.

It is usually one sort plus one pass: fast and short. But it is only correct when you can argue that the local best choice never blocks the best overall answer.

So greedy is two skills: spotting the safe choice, and proving it safe (or breaking it with a tiny counter-example and switching to DP).

picture this

Your download manager has five files queued on one connection. To make the average wait smallest, start the smallest file first. If a big file ever runs just before a smaller one, swap them: the small one finishes earlier, and the pair still ends at the same moment. Every such swap helps, so shortest-first wins. That swap is the exchange argument, the proof behind most greedy answers.

03 · remember

What you must know

  • Greedy choice property: some best answer starts with the greedy choice. Optimal substructure: after that choice, what's left is a smaller copy of the same problem. You need both.
  • Exchange argument: take any best answer. Swap its first choice that differs from greedy's for the greedy one. Show it's still valid and no worse. Repeat, and the best answer becomes the greedy answer.
  • Greedy stays ahead: show that after every step, greedy's state is at least as good as anyone else's. Jump Game's reach is never behind any other sequence of jumps.
  • Greedy can be wrong. Coins {1, 3, 4}, amount 6: biggest-first pays 4+1+1 (3 coins), but 3+3 is 2. When no proof works, or a tiny input breaks it, use DP.
  • Furthest reach: in Jump Game the reachable indices always form a prefix [0..reach], so one integer replaces a whole search. Jump Game II counts BFS levels with two integers.
  • Restart past a failure: in Gas Station, if the tank goes negative at i, no start in [start..i] can work, so jump straight to i + 1. One pass.
  • Keep a range of possibilities: when a choice is unknown (a * in LC 678), track the smallest and largest possible state instead of trying every choice.
  • Filter, then combine: in Merge Triplets, anything that overshoots the target is useless forever, and everything else is harmless to merge.
  • Two passes for two-sided rules: Candy satisfies "more than the left neighbour" in one pass and "more than the right" in another, then takes the max.
  • Forced choices: in Hand of Straights the smallest card must start a group, because nothing smaller is left to come before it.
  • Typical cost: O(n) for the pass, O(n log n) if you sort first. Intervals (next chapter) are greedy's biggest family.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

When greedy fails: biggest coin first

Try coins 1, 3, 4 with amount 6. Then try 1, 2, 5, 10, where greedy happens to be right.

loading simulation…
sim

Jump Game: one number of state

Only the furthest reachable index matters. If `i` ever passes it, you're stuck.

loading simulation…
sim

Gas Station: restart past a failure

When the tank goes negative, every start so far is ruled out at once. `total` decides whether any start works.

loading simulation…
sim

Valid Parenthesis String: a range instead of a guess

The green cells are every open count still possible. A `*` widens the range; `)` and `(` shift it.

loading simulation…
sim

Partition Labels: stretch to the last index

Each letter drags the piece's end to its last occurrence. When `i` reaches `end`, cut.

loading simulation…

05 · cost

Time & space, explained

Jump Game three ways
TimeExtra spacewhy
Try every jump (recursion)O(2ⁿ)O(n)Paths multiply at every index, and the same index is solved again and again. The stack is up to n deep.
DP: can you finish from index i?O(n²)O(n)Each index may scan up to n later indices. One boolean per index.
Greedy furthest reachO(n)O(1)One pass and one integer: the reachable indices are always a prefix.
This chapter's greedy moves
TimeExtra spacewhy
Fewest jumps as BFS levels (LC 45)O(n)O(1)end and farthest replace a queue, because every level is one contiguous range.
Restart after a negative prefix (LC 134)O(n)O(1)Each station adds its gain to tank and total once.
Filter, then combine (LC 1899)O(n)O(1)One look per triplet and three booleans.
Stretch to the last index (LC 763)O(n)O(1)Two passes; last[26] has a fixed size whatever n is.
Range of possibilities (LC 678)O(n)O(1)Two ints, lo and hi, updated once per character.
Two passes (LC 135)O(n)O(n)One candies array, filled left to right and then right to left.
Smallest card starts a run (LC 846)O(n log n)O(n)Every card is counted and consumed once, at O(log n) per TreeMap call.
Shortest job firstO(n log n)O(n)The sort dominates; the copy keeps the caller's array untouched.
Coins: greedy vs DP (k coin values, amount A)
TimeExtra spacewhy
Biggest coin firstO(k log k)O(k)Sort the k values, then one division per value. Fast, but only right for canonical coin systems.
DP over every amountO(A · k)O(A)Each amount 1..A tries every coin once. Always right.

06 · java

Raw vs Collections Framework

The greedy template: sort, then one pass

javashortest job firstjava.util.*
class ShortestFirst {    /** Jobs run one after another from time 0. Returns the smallest possible sum of finish times. */    static long totalFinishTime(int[] durations) {        int[] jobs = durations.clone();     // don't reorder the caller's array        Arrays.sort(jobs);                  // greedy rule: shortest job first        long clock = 0, total = 0;          // long: 10^5 jobs x 10^4 minutes overflows int        for (int d : jobs) {            clock += d;                     // this job finishes at `clock`            total += clock;        }        return total;    }}
  • Sort by the key that makes the safe choice obvious, then make one decision per item with a few variables of state.
  • Arrays.sort(int[]) sorts primitives with a dual-pivot quicksort: O(n log n) on average, no boxing.
  • durations.clone() first: sorting in place would reorder the caller's array behind their back.
  • Sums of times grow fast. 10⁵ jobs of 10⁴ minutes add up to about 5 × 10¹³, far past int's 2.1 × 10⁹, so clock and total are long.

When greedy fails: biggest coin vs DP

javabiggest coin firstjava.util.*
class GreedyCoins {    /** "Biggest coin first". Correct for {1, 2, 5, 10, ...}; WRONG for coin sets like {1, 3, 4}. */    static int greedyCoins(int[] coins, int amount) {        int[] sorted = coins.clone();        Arrays.sort(sorted);        int count = 0;        for (int i = sorted.length - 1; i >= 0 && amount > 0; i--) {            int take = amount / sorted[i]; // as many of this coin as fit            count += take;            amount -= take * sorted[i];        }        return amount == 0 ? count : -1; // -1: greedy got stuck    }}
  • Biggest-first is right for canonical coin systems. The rupee system ₹1, 2, 5, 10, 20, 50, 100, 200, 500 is one: GreedyBasics.java checks every amount up to ₹3,000 against the DP.
  • It is wrong for {1, 3, 4} at amount 6, and it gets stuck for {3, 5} at amount 9 (taking 5 leaves 4, which 3 can't pay).
  • The DP is the safe fallback: dp[a] = min(dp[a - c] + 1) over every coin c. LC 322 Coin Change is exactly this.

Forced choices: sorted array + HashMap vs TreeMap

javasort once + HashMapjava.util.*
class Solution {    public boolean isNStraightHand(int[] hand, int groupSize) {        if (hand.length % groupSize != 0) return false;        int[] cards = hand.clone();        Arrays.sort(cards);                                 // smallest card first, once        Map<Integer, Integer> count = new HashMap<>();        for (int c : cards) count.merge(c, 1, Integer::sum);        for (int c : cards) {            if (count.get(c) == 0) continue;                // already used inside an earlier run            for (int k = 0; k < groupSize; k++) {           // c must START a run: c, c+1, ..., c+groupSize-1                int have = count.getOrDefault(c + k, 0);                if (have == 0) return false;                // gap in the run                count.put(c + k, have - 1);            }        }        return true;    }}
  • TreeMap is a red-black tree: firstKey(), get, put and remove are O(log n), and it always knows the smallest key.
  • count.merge(c, 1, Integer::sum) adds one to a count in a single call, inserting 1 if the key is new.
  • Sorting once and walking the sorted array gives the same "smallest first" order with a plain HashMap. Same O(n log n), fewer tree operations.

Uncertain choices: a range vs two stacks

javarange [lo, hi]java.util.*
class Solution {    public boolean checkValidString(String s) {        int lo = 0, hi = 0; // fewest and most '(' that could still be open        for (char c : s.toCharArray()) {            if (c == '(') {                lo++;                hi++;            } else if (c == ')') {                lo--;                hi--;            } else { // '*': ')' lowers lo, '(' raises hi                lo--;                hi++;            }            if (hi < 0) return false; // too many ')' even if every '*' is '('            lo = Math.max(lo, 0); // a count below 0 is never a real choice        }        return lo == 0; // some choice closes every '('    }}
  • The range version keeps two ints and never decides what a star is. O(1) space.
  • The stack version stores indices in ArrayDeques (push/pop are O(1)). It does decide: each ')' uses a real '(' first, then a star.
  • At the end, a leftover '(' needs a star that comes after it. That's why the stacks hold indices, not characters.
Java API you will actually use
calldoescost
Arrays.sort(int[] a)Sort primitives (dual-pivot quicksort)O(n log n)
Math.max(a, b) / Math.min(a, b)Update reach, farthest, a clamp or a candy countO(1)
Arrays.fill(a, 1)Give every child one candy to startO(n)
new TreeMap<Integer, Integer>()Counts kept in key order (red-black tree)O(1) to build
map.merge(k, 1, Integer::sum)Add one to a count, inserting 1 if absentO(log n) TreeMap · O(1) avg HashMap
treeMap.firstKey()Smallest key still presentO(log n)
map.getOrDefault(k, 0)Read a count that may be missingO(1) average (HashMap)
Deque<Integer> st = new ArrayDeque<>()Stack of indices: push, pop, isEmptyO(1) per op

Can you reach the end? Fewest jumps?

→ Two or three ints: reach, end, farthest

Reachable indices form a prefix, and BFS levels are ranges.

A circular route with a running balance

→ tank + total, restart at i + 1

A failed prefix rules out every start inside it; total says if any start works.

The smallest remaining item must be used next

→ TreeMap (or sort once + HashMap)

firstKey() is O(log n); sorting once is faster in practice.

A wildcard that can mean several things

→ A range [lo, hi] of possible states

Covers every choice at once with O(1) space.

Rules from both neighbours

→ Two passes over one int[]

Each pass fixes one direction; max keeps both.

No proof, or a 3-element counter-example breaks it

→ Dynamic programming

DP tries every choice, so a locally good move can't fool it.

07 · recognise

Spot the pattern

"Can you reach the end?" / "fewest jumps"

Furthest reach; BFS levels without a queue

Circular route with a running balance

Gas Station: restart after any prefix that goes negative

Constraints from both neighbours (left and right)

Two passes, one per direction (Candy)

"Split into as many parts as possible" with a last-occurrence rule

Partition Labels: stretch the end to the last index

A wildcard like * that can be several things

Track the range of possible states (lo, hi)

"Combine with max (or min) any number of times"

Throw away anything that overshoots; the rest is harmless

"Split into groups of consecutive values"

The smallest value must start a group (TreeMap)

"Order jobs to minimise total or average waiting"

Shortest first, proved by an exchange argument

Coins or weights with arbitrary values, "minimum number"

Be suspicious of greedy. Try a counter-example, then use DP

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Using greedy without a proof. Always try 2–3 tiny counter-examples first (coins {1, 3, 4}, amount 6).
  • Jump Game II: looping to i < n instead of i < n - 1. That adds one extra jump when you land exactly on the end.
  • Gas Station: forgetting the total >= 0 check. The restart trick finds a candidate, but only the total says whether any start works.
  • Candy: writing candies[i] = candies[i + 1] + 1 in the second pass without max, which throws away the first pass's work.
  • Valid Parenthesis String: skipping the hi < 0 check or the clamp lo = max(lo, 0). Each one alone gives wrong answers.
  • Summing waiting times in int. 10⁵ jobs × 10⁴ minutes overflows; use long.
  • Sorting the caller's array when they still need its order. Clone it first.

tricks

  • Say the greedy rule and its one-line proof before coding. That proof is what the interviewer is grading.
  • Bas itna yaad rakho: if you can't say why the choice is safe, it probably isn't. Write the DP; a correct slower answer beats a fast wrong one.
  • Ask yourself: "What's my one variable of state?" (reach, tank, lo/hi, end). Most greedy answers are 5–10 lines.
  • Edge cases to test: one element, all equal, strictly rising, strictly falling, zeros, and the answer sitting at the very end.
  • Stuck between greedy and DP? Write the O(n²) DP first. It's often the clue to the greedy: watch which DP choice always wins.

09 · why & how

Questions you might be too shy to ask

How do I know a problem is greedy and not DP?

Look for a choice that is always safe, no matter what comes later. Then try to break it with tiny inputs (2–4 items). If every small test passes and you can say why the choice can't hurt, it's greedy. If one small input breaks it, the problem needs DP (or backtracking).

Greedy and DP both pick the best option. What's the actual difference?

DP compares every option, each with its future already solved, and then picks the best. Greedy picks one option by a simple rule and never looks at the other options' futures. Coins {1, 3, 4}, amount 6: DP checks 6 − 4, 6 − 3 and 6 − 1, and sees that 6 − 3 = 3 needs just one more coin. Greedy grabs the 4 and is stuck paying 1 + 1. That's why greedy needs a proof and DP doesn't.

What is an exchange argument, in plain words?

Take any optimal answer. Look at the first place it differs from the greedy answer. Swap in the greedy choice and show the result is still valid and no worse. After enough swaps, the optimal answer is the greedy answer, so greedy is optimal. For the download queue: if a bigger file runs just before a smaller one, swapping them saves exactly (bigger − smaller) minutes of total waiting.

What does "greedy stays ahead" mean?

Instead of swapping, you compare progress. Show that after every step, greedy's state is at least as good as any other solution's. In Jump Game, reach is the furthest any sequence of jumps could have got so far, so if greedy gets stuck, everyone does.

Most greedy answers start with a sort. How do I pick what to sort by?

Sort so the safe choice comes first. The "best" item is not always the biggest: it's the shortest job (waiting time), the smallest card (Hand of Straights), the furthest reach (Jump Game). Write down 2–3 candidate keys, test each on a tiny input, and keep the one you can defend with a swap. The next chapter, Intervals, is full of exactly this question: sort by start or by end?

How do I find a counter-example fast?

Keep inputs tiny (2–4 items) and try the shapes that fool greedy: one big item that blocks two medium ones (coins {1, 3, 4}, amount 6), equal values, all rising, all falling. Work out the true best answer by hand — with 3 items you can list every option. If greedy loses even once, stop: the problem needs DP or backtracking.

Why is Jump Game II greedy and not BFS?

It is BFS, just without a queue. All indices reachable with k jumps form one contiguous block (a level). end marks the edge of the current level, and farthest builds the next one. Reaching end means one more jump. Since the levels are contiguous ranges, two integers replace the queue.

Jump Game II: which index do I actually jump to? The one with the biggest number?

Not the biggest number — the biggest reach, i + nums[i]. In [3, 4, 1, 3, 1, 1, 1], from index 0 you can land on 1, 2 or 3. Index 1 has the biggest value (4) but reaches only index 5; index 3 reaches 3 + 3 = 6, the end. Biggest value costs 3 jumps, biggest reach costs 2. The level loop never names the index — farthest quietly tracks the best reach for you.

In Gas Station, why can we skip every start between the old start and i?

Say you start at s and the tank first goes negative at i. Pick any start k between s + 1 and i. Starting fresh at k, your tank at k is 0. Coming from s, you reached k with a tank of 0 or more. So from k onwards the fresh tank is never fuller than the old one — and the old one already ran dry at i. So none of s..i works, and the next candidate is i + 1.

Gas Station: why does total >= 0 guarantee the last candidate really works?

The restarts cut the circle into failed pieces (each sums to less than 0), then the last stretch from the candidate to the end, which never went negative and leaves a tank of T ≥ 0. Keep driving from the end into the failed pieces: inside a piece, the tank only drops below its level at that piece's start at the piece's last station. So the lowest it can ever be is T + (all failed pieces) = total ≥ 0. It never runs dry, and you get back to the candidate.

Why does biggest-coin-first work for rupees but not for {1, 3, 4}?

Coin systems where greedy is always right are called canonical. ₹1, 2, 5, 10, 20, 50, 100, 200, 500 is canonical: this chapter's Java checks every amount up to ₹3,000 against DP. {1, 3, 4} isn't: at 6, taking the 4 leaves 2, which costs two 1s. Kozen and Zaks proved that if greedy fails at all, it already fails below the sum of the two biggest coins, so a short check finds the counter-example.

If greedy is so fast, why learn DP at all?

Because greedy is only correct when one locally best choice is always safe (the greedy choice property). That set is small and easy to get wrong. DP is the safe general tool. Greedy is the shortcut you take once you've proved it's safe.

Do I have to write a formal proof in an interview?

No. One or two sentences is enough: name the choice, then say why swapping it into any best answer can't hurt, or why your state is never behind. The interviewer wants to hear that you checked, not a page of maths.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #55
    Jump Gamemust-do
    MediumAdobeAmazonBloombergMicrosoftGoogle+1
  2. #45
    Jump Game IImust-do
    MediumAmazonMicrosoftBloombergGoogleAdobe
  3. #134
    Gas Stationmust-do
    MediumFlipkartInfosysBloombergAmazonMicrosoft+1
  4. #1899
    Merge Triplets to Form Target Triplet
    MediumGoogle
  5. #763
    Partition Labels
    MediumAmazonGoogleMeta
  6. #678
    Valid Parenthesis Stringmust-do
    MediumByteDance / TikTokAmazonMetaGoogle
  7. #846
    Hand of Straights
    MediumGoogleAmazon
  8. #135
    Candy
    HardAmazonMicrosoftGoogle

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #322
    Coin Change
    Mediumin Dynamic Programming

    Where biggest-coin-first breaks: the DP answer to this chapter's counter-example.

  2. #621
    Task Scheduler
    Mediumin Heaps

    Greedy with a heap: always run the task with the most copies left.

  3. #121
    Best Time to Buy and Sell Stock
    Easyin Arrays & Strings

    A one-pass greedy: remember the cheapest price so far.

11 · revise

The whole chapter on one screen

8 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    Greedy = take the best-looking choice now and never undo it. Fast (one sort + one pass), but only right with a proof.

  2. use it when

    One choice is always safe: furthest reach, restart after a failure, smallest card first. Can't say why in one line? Suspect DP.

  3. template

    Sort by the key that makes the choice obvious → one loop → a few variables of state (reach, tank, lo/hi).

  4. cost

    Usually O(n) for the pass, O(n log n) with a sort. DP for the same problem is often O(n²); brute force is 2ⁿ.

  5. trap

    Coins {1, 3, 4}, amount 6: biggest-first pays 4+1+1 (3 coins), but 3+3 is 2. Test 2–3 tiny inputs before trusting greedy.

  6. trap

    Gas Station: the restart finds a candidate, but only total >= 0 says a start exists. Skip it and you return a wrong index.

  7. pro tip

    Prove it out loud: exchange (swap any best answer's choice for mine, no worse) or stays ahead (my reach is never behind).

  8. pro tip

    Unknown choices? Track a range. LC 678 keeps lo/hi open counts instead of trying all 3ᵏ meanings of the stars.

12 · recall

Flip, remember, repeat

card 1 / 13
recall

Which two properties make a greedy algorithm correct?

tap or Space to flip ↻

Question 1: Which two properties make a greedy algorithm correct?

13 · check yourself

Quick quiz

  1. Coins {1, 3, 4}, amount 6. What does biggest-coin-first return, and what is optimal?

  2. Jobs of 4, 1 and 3 minutes run one after another. Which order gives the smallest total of finish times?

  3. Jump Game: nums = [1, 0, 2]. At i = 1, reach = 1. What happens at i = 2?

  4. Jump Game II on [2, 3, 1, 1, 4]: at i = 0, end = 0 and farthest becomes 2. What happens?

  5. Gas Station: the tank first goes negative at station 4 with start = 1. Which start do you try next?

  6. Valid Parenthesis String: after reading "(*", what is the range [lo, hi] of possible open counts?

  7. Candy: ratings [1, 2, 2]. What is the minimum total?

  8. Which problem is safely solved by greedy?

0/0 correct · 8 left

14 · learn more

A second teacher, if you want one