Greedy

The greedy coding pattern for interviews. When a local choice is safe, the exchange argument, Kadane's algorithm and farthest reach, with a step-through, templates in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Mid-level14 min read

A greedy algorithm makes the choice that looks best right now, and never goes back on it. Take the meeting that ends first. Drop a running sum once it turns negative. Jump to wherever reaches farthest. There is no search over options and no table of answers, so greedy solutions are short and fast, often one O(n) pass over n items.

The catch is that a greedy choice is often wrong. Paying 6 with coins of 1, 3 and 4, the biggest coin first gives 4 + 1 + 1, three coins. But 3 + 3 is two. So the code is the easy part. The real work is the argument that the local choice can never block the best answer. With that argument, greedy is the best solution there is. Without it, you need dynamic programming.

How to spot it

“Maximum number of”, “minimum number of” with a choice at each step, and a natural order: earliest end, smallest size, highest value.
Scheduling, intervals or assigning items to people, rooms or slots.
A running total that can go bad, like a sum that turns negative or a gas tank that runs dry. Once it’s bad, starting over can only be better.
Reachability on a line: “can you reach the end”, “fewest jumps”.
The DP has only one useful choice per state. Then the table collapses to a single variable, and DP becomes greedy.

It’s probably not greedy when a small example breaks the obvious choice, as with coins of 1, 3 and 4. It’s also not greedy when choices interact far apart, as in 0/1 knapsack, where taking one item changes which later items fit.

Watch it run

Two examples. In Kadane’s algorithm for the largest subarray sum, the window is the best subarray ending at i. When its sum drops below 0, it’s dropped. In Jump Game, reach is the farthest index any path can get to so far. Switch to it with the button above the demo.

nums

-2011-3243-142516-5748

best_ending_here best sum ending here

-2

best best so far

-2

best_ending_here = best = nums[0]
for number in nums[1:]:
best_ending_here = max(number, best_ending_here + number) # or restart
best = max(best, best_ending_here)
return best

Find the subarray with the largest sum. The window is the best subarray that ends at i.

1 / 14

Both keep one number instead of a list of options. Kadane doesn’t remember which subarrays it skipped. It knows that a negative prefix can only make any later sum smaller. Jump Game doesn’t remember which jumps it took. Every index up to reach can be reached, so the only fact that matters is how far that is.

The template

Kadane’s maximum subarray, Jump Game, and the fewest jumps:

Greedy.javaexample.pyGreedy.csmain.goexample.ts

public class Greedy {
    static int maxSubArray(int[] nums) {
        // Kadane's algorithm: the best subarray ending at i either extends the best one ending
        // at i - 1, or starts fresh at i. A negative running sum can only hurt what comes after,
        // so drop it. O(n) time for n numbers, O(1) memory.
        int bestEndingHere = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // Extend, or start over at nums[i].
            bestEndingHere = Math.max(nums[i], bestEndingHere + nums[i]);
            best = Math.max(best, bestEndingHere);
        }
        return best;
    }

    static boolean canJump(int[] nums) {
        // Can we reach the last index? Keep the farthest index reachable so far. Every index up
        // to reach is reachable, so we never need to know which jumps got us there. O(n) time,
        // O(1) memory.
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false; // no jump lands this far, so i and the rest are cut off
            reach = Math.max(reach, i + nums[i]);
        }
        return true;
    }

    static int jump(int[] nums) {
        // Fewest jumps to the last index. Think in rounds, like BFS: the indexes reachable with the
        // same number of jumps form one block, and the next block ends at the farthest jump from
        // inside it. O(n) time.
        int jumps = 0, end = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) { // the last index needs no jump from it
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) { // the current block is used up, so one more jump is needed
                jumps++;
                end = farthest;
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        check(maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}) == 6);
        check(maxSubArray(new int[] {5, 4, -1, 7, 8}) == 23);
        check(maxSubArray(new int[] {-3, -1, -2}) == -1);
        check(canJump(new int[] {2, 3, 1, 1, 4}));
        check(!canJump(new int[] {3, 2, 1, 0, 4}));
        check(canJump(new int[] {0}));
        check(jump(new int[] {2, 3, 1, 1, 4}) == 2);
        check(jump(new int[] {0}) == 0);
        System.out.println("ok: maxSubArray, canJump and jump");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

jump is greedy in rounds, like BFS. The indexes you can reach with the same number of jumps form one block, from the end of the last block to end. While walking through a block, keep the farthest index any of them reaches. When you reach end, you must jump again, and the next block ends at that farthest index.

Variations

Sort, then take in order

Many greedy problems are “sort by the right key, then walk once”. Assign Cookies sorts children and cookies, and gives each child the smallest cookie that is big enough. Keeping the most non-overlapping intervals sorts by end time, as on the intervals page. Choosing the key is the whole problem. Try two or three keys on a small example before you commit.

The exchange argument, worked

Take interval scheduling. Let greedy_pick be the interval that ends first. Take any best answer, and let best_pick be its first interval. greedy_pick ends no later than best_pick, so swapping best_pick for greedy_pick can’t create an overlap with the rest. The new answer is just as big, and it starts with greedy_pick. So choosing greedy_pick was safe. Now repeat the argument on what is left. In an interview, say this in three sentences. That’s what turns “it feels right” into a proof.

Reset when it goes bad

Gas Station walks the stations with a running tank. If the tank goes negative at station i, no start between the last start and i can work. Each of them would arrive at i with even less gas. So jump the start to i + 1 and reset the tank. Kadane is the same idea with sums. Both are one O(n) pass.

Kadane with products

Maximum Product Subarray looks like Kadane, but a negative number can turn the smallest product into the largest. Keep both the largest and the smallest product ending at i. That’s two variables instead of one, which is really a tiny DP. It shows where greedy ends and DP begins.

Complexity

	Time	Extra memory
Kadane, Jump Game, Jump Game II	O(n)	O(1)
Gas Station	O(n)	O(1)
Sort, then one pass	O(n log n)	O(1) to O(n)
Jump Game done as DP instead	O(n²)	O(n)

Say this out loud

A negative running sum can only make every later sum smaller. So at each index I either extend the current subarray or start fresh, whichever is bigger, and keep the best seen. That’s one pass, O(n) time and O(1) memory.

Interview questions

Interviewer asksHow do you prove a greedy solution is correct?

Use an exchange argument. Take any best answer and compare it with the greedy one at the first place they differ. Show that swapping in the greedy choice keeps the answer valid and no worse. Repeat, and the best answer turns into the greedy one without losing anything. Another way is “greedy stays ahead”: after every step, greedy is at least as far along as any other answer.

Interviewer asksKadane returns the sum. How do you also return where the subarray is?

Keep a start index. When the running sum restarts at i, set start = i. When the running sum beats the best, save (start, i) as the best range. It’s still one pass and O(1) memory. If every number is negative, the answer is the single largest number. Starting best_ending_here and best at nums[0] handles that.

Interviewer asksJump Game: why isn't this a graph search?

It could be. Each index is a node, and each jump is an edge. BFS would work, but there can be O(n²) edges. Greedy works because the reachable indexes always form one block with no gaps. If index j is reachable, so is every index before it. So one number, the end of the block, says everything a search would find.

Practice

10 problems on LeetCode: 2 easy, 7 medium, 1 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Two of these are solved step by step on this site, as part of the Blind 75: Maximum Subarray and Jump Game. Three more use the same greedy ideas: Non-overlapping Intervals (sort by end), Best Time to Buy and Sell Stock (keep the lowest price so far) and Maximum Product Subarray (Kadane with two variables).

Recap

Use it when each step has an obvious best choice, and you can argue that the choice never blocks the best answer.
Prove it with an exchange argument, or show greedy stays ahead after every step.
Common shapes: sort and take in order, reset a running total when it goes bad, track the farthest reach.
Cost: usually O(n), or O(n log n) with a sort, and O(1) memory.
Watch for: greedy ideas that fail on a tiny example. Then use dynamic programming.