Greedy algorithms

Here is a greedy algorithm you already run every day: making change. To give back 68 with notes of 50, 10, 5, and 1, a cashier does not solve an equation. She takes a 50, then a 10, then a 5, then three 1s. Each step takes the largest note that still fits. That is greedy: break a large problem into a sequence of small decisions, take the best-looking option at each one, and never go back.

That example works. But it works because of these particular note values, not because greedy always works. Change the values to 1, 3, and 4 and ask for 6: greedy takes the 4 first and needs three coins, while 3 + 3 needs only two. Same method, same kind of problem, wrong answer. Section 07 takes that example apart.

Compare greedy with the two approaches you already know. Backtracking (chapter 05) tries every choice and undoes the ones that lead nowhere: always correct, but exponential. Dynamic programming (next chapter) also considers every choice, but stores the answer of each subproblem so it is computed once: always correct, and polynomial. Greedy goes further than both: it keeps exactly one choice per step and throws the rest away. That is why it usually runs in O(n) or O(n log n), and it is also why it needs a proof. Dropping the other choices is only safe if you can show none of them was needed.

The problem: each child i has an appetite g[i], and each cookie j has a size s[j]. One cookie goes to at most one child, and the child is satisfied only if s[j] ≥ g[i]. How many children can be satisfied at most?

The greedy rule: sort both arrays, then give the child with the smallest appetite the smallest cookie that is still large enough. If the smallest remaining cookie is too small even for that child, it is too small for every child, so discard it. Watch it run once before reading the proof.

The code is a sort plus one pass with two pointers. Short code is not the same as correct code, so the important question is why this rule cannot lose.

Now the proof. The tool is the exchange argument, and it is the template behind almost every greedy correctness proof in this chapter. The idea in one sentence: take any optimal solution that disagrees with the greedy choice, and rewrite it so that it agrees, without making it worse. If such a rewrite always exists, then some optimal solution contains the greedy choice, so making that choice loses nothing. Three steps:

The lightest kind of greedy: one linear scan, with a small decision at each element based on its relation to the previous one. Start with LC 376 Wiggle Subsequence. A wiggle sequence is one where consecutive differences are non-zero and alternate in sign: up, down, up, down. The task is to find the longest wiggle subsequence.

The greedy observation: treat a stretch of equal values as a single value, then cut the array into maximal runs that go only up or only down. Inside a run, the middle elements contribute nothing, because they do not change direction. Keeping only the last element of each run keeps the wiggle just as long, so if there are k runs, the answer is k + 1 (the last element of each run, plus the first element of the array). In [1, 4, 7, 2, 5] the runs are 1→7, 7→2, and 2→5, so k = 3 and the answer is 4. The 4 in the middle is one stop on the way up (grey); the endpoints and the turning points 7 and 2 are what count (highlighted):

LC 53 Maximum Subarray (review): the greedy reading of Kadane's algorithm is if the sum carried in from the left is negative, it can only make the next subarray smaller, so drop it. That is cur = max(nums[i], cur + nums[i]), while tracking the largest cur seen. The same line is also a one-dimensional DP where cur is the largest sum of a subarray ending at index i. Chapter 07 teaches it in full, with a cell-by-cell animation. Here it is only a reminder that one problem can have two justifications.

LC 55: each number says how many steps forward you may jump from that cell. Can you get from index 0 to the last index? Brute force tries every jump length from every cell, which is exponential. The greedy observation: you never need to know which jumps to make. It is enough to track the farthest index reachable so far. The invariant is: when the scan arrives at index i and i ≤ reach, every index from 0 to i is reachable from the start, and reach is the farthest index reachable using cells 0 to i as launch points. So if i > reach, index i is unreachable, and because movement is forward only, nothing beyond it is reachable either. Here is the case where the range falls one cell short:

LC 55 needs three lines: reach = max(reach, i + nums[i]), return false if i > reach, and return true at the end. Turning "can you arrive" into "in how few jumps" gives LC 45 Jump Game II.

Brute force or DP: let dp[i] be the fewest jumps to reach i, and for each i look back at every cell that can jump to it. That is O(n²). Why O(n) is possible: group the indices into layers. Layer 1 is everything reachable in one jump, layer 2 everything reachable in two, and so on. The scan keeps two numbers: curEnd, the last index of the current layer, and farthest, the last index of the next layer. While walking inside a layer it only records how far the next layer could go; it counts a jump exactly when it reaches the end of the current layer. The invariant is that after k counted jumps, curEnd is exactly the farthest index reachable in k jumps, so the layer that first contains the last index gives the minimum. Step through it:

These problems have no clever sorting trick. You work out one local rule and then simulate it in a single pass. All of the difficulty sits in one question: why does following that rule never cost you later?

LC 860 Lemonade Change (warm-up): customers pay with 5, 10, or 20, and you give change from the bills you have received. A 5 needs no change, a 10 needs one 5, and a 20 needs either 10 + 5 or 5 + 5 + 5. The rule: prefer 10 + 5. Here is the exchange argument in one step. Choosing 10 + 5 leaves you with two more 5s and one fewer 10 than the other option. Suppose a later customer forces you to use a 10 you no longer have. You can pay that 20 with 5 + 5 + 5 instead, which costs exactly those two extra 5s. So preferring 10 + 5 never turns a case you could have served into one you cannot.

LC 135 Candy (hard, but the pattern is clear): every child has a rating, a child with a higher rating than a neighbor must get more candy than that neighbor, and everyone gets at least one. Minimise the total. The difficulty is that each child is constrained from the left and from the right at the same time. The fix is one direction per pass: going left to right, satisfy "more than the left neighbor"; going right to left, satisfy "more than the right neighbor"; take the maximum so both hold. Why the result is minimal: each pass produces the smallest values that satisfy one side, so both are lower bounds for any valid answer, and so is their maximum. That maximum is itself valid, so it is the smallest valid assignment at every position, and therefore has the smallest total.

Almost every interval problem starts with a sort, and the choice of sort key decides whether it works. The main example is LC 435 Non-overlapping Intervals: given a set of intervals, remove as few as possible so that the rest do not overlap.

Brute force: try every subset to keep, which is 2ⁿ. The greedy observation: removing the fewest is the same as keeping the most non-overlapping intervals. To keep many, always keep the interval that ends earliest, because it leaves the largest amount of time for everything after it. So sort by right endpoint, scan left to right, keep an interval when it does not overlap the last kept one, and delete it otherwise. Step through the timeline:

Why the end, and not the start? The exchange argument: let OPT be an optimal set of kept intervals, listed in order, and let X be its first interval. G, the interval that ends earliest of all, satisfies end(G) ≤ end(X). Replace X by G. The remaining intervals of OPT all start at or after end(X), so they start at or after end(G) as well, and the set is still non-overlapping and just as large. Repeat on the rest, and greedy keeps as many as any optimal solution.

The other two sort keys really do fail. Sorting by start time and keeping greedily: on [0,10], [1,2], [3,4], you keep [0,10] and end with 1 interval, while the best answer is 2. Sorting by shortest length: on [0,5], [4,6], [5,10], the shortest is [4,6], which overlaps both others, so you end with 1 interval instead of 2. Neither of those rules survives an exchange argument, and each has a three-interval counterexample.

You now have a fast tool, and the warning from the start of the chapter still applies: greedy can fail. The clearest failure is the opening example of the next chapter, LC 322 Coin Change, with coins [1, 3, 4] and amount 6. Try it yourself and watch greedy miss the best answer:

Why does greedy fail here? Because the coin set [1, 3, 4] does not have the greedy-choice property. Taking the 4 first is the locally best move, and it destroys the structure of the best answer, 3 + 3. There is no exchange argument to write, because the counterexample is right there. No proof, no greedy. The fallback is DP: enumerate which coin is used last, and store the answer of each subproblem. Chapter 07 does exactly that, with a cell-by-cell animation of dp[6]. Note also that the same greedy rule is optimal for other coin sets, such as 1, 5, 10, 25 — which is why the property has to be checked per coin set, not assumed.