Greedy

At a glance

The instinct

A greedy algorithm makes the choice that looks best right now and never revisits it. That is only correct when the problem has the greedy-choice property: some optimal solution begins with your greedy choice, and what remains is a smaller version of the same problem. Greedy code is usually short; the hard part is believing it.

In Jump Game II you never decide "which" jump to take: you scan the current reachable range, remember the farthest point any of it can reach, and only spend a jump when the range runs out. In Gas Station, if total gas covers total cost a start exists, and whenever the running tank goes negative, no station in that stretch can be the start - so restart after it.

Recognise it

Not this pattern if...

• A tiny counterexample breaks your rule: coins {1, 3, 4} and amount 6 - greedy pays 4+1+1 (3 coins), the best is 3+3 (2 coins). Use DP.
• Choices interact so an early pick changes the value of later ones (0/1 knapsack) - DP.
• You must list every valid answer - backtracking.
• The answer is monotonic in a parameter but there is no obvious local rule - binary search on the answer, often with a greedy feasibility check inside.

Memory hack

Analogy - the cashier. Handing out change with the largest note first is perfect for real currencies, which are designed so that greedy works. Invent a currency with 1, 3 and 4 coins and the same habit gives the wrong answer for 6. The habit did not change - the structure of the problem did. That is why every greedy solution needs a reason, not a feeling.

Say it out loud:

1. "My rule: always pick ___ (after sorting by ___)."
2. "Counterexample hunt: I tried ___ and ___ and the rule held."
3. "Why it's safe: take any optimal answer; swapping its first choice for mine is never worse (exchange argument), or my partial answer is always at least as far ahead (stays ahead)."

How it works

Two proof styles cover most interview problems. Exchange argument: show any optimal solution can be rewritten to start with your choice without getting worse, then repeat on the remainder. Stays ahead: show that after every step your greedy partial solution is at least as good as any other partial solution of the same length.

Trace of Jump Game II on [2, 3, 1, 1, 4] (loop stops before the last index):

Answer: 2 jumps. It is really a BFS where each "layer" is the range reachable with the current number of jumps.

Java template

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

class GreedyTemplates {
    // 1) Sort, then scan: commit to each compatible item in the chosen order.
    static int maxNonOverlapping(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[1], y[1])); // greedy key: earliest finish
        int count = 0;
        long lastEnd = Long.MIN_VALUE;
        for (int[] iv : intervals) {
            if (iv[0] >= lastEnd) { count++; lastEnd = iv[1]; }        // take it and never undo
        }
        return count;
    }

    // 2) Reach expansion (Jump Game II): spend a jump only when the current range is used up.
    static int minJumps(int[] nums) {
        int jumps = 0, end = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) { jumps++; end = farthest; }
        }
        return jumps;
    }

    // 3) Deferred choice with a heap (refuelling): remember options, use the best only when forced.
    static int minRefuelStops(int target, int fuel, int[][] stations) { // stations sorted by position
        PriorityQueue<Integer> passed = new PriorityQueue<>(Collections.reverseOrder());
        long reach = fuel;
        int stops = 0, i = 0;
        while (reach < target) {
            while (i < stations.length && stations[i][0] <= reach) passed.offer(stations[i++][1]);
            if (passed.isEmpty()) return -1;                           // stuck: nothing to refuel from
            reach += passed.poll();
            stops++;
        }
        return stops;
    }
}

Complexity

• Sort then scan: O(n log n) time, O(1) to O(log n) extra space for the sort.
• Single scan with a counter or reach: O(n) time, O(1) space (Jump Game, Gas Station, parentheses).
• Two-pass arrays: O(n) time, O(n) space (Candy).
• Sort + heap: O(n log n) time, O(n) or O(k) heap space (Minimum Cost to Hire K Workers, refuelling).
• Counting formula: O(n) to count frequencies, O(1) for the formula (Task Scheduler).

Variations

• Reach / coverage - keep the farthest reachable point. Jump Game, Jump Game II.
• Running balance with reset - Gas Station; a balance counter that fixes deficits on the spot - Minimum Add to Make Parentheses Valid.
• Interval scheduling - sort by end time, take what fits; sort by start time when merging instead.
• Two-pass neighbour constraints - satisfy the left rule, then the right rule. Candy.
• Frequency formula - the most frequent item dictates the layout. Task Scheduler.
• Fix one dimension, optimise the other - sort by ratio, keep the smallest qualities in a max-heap. Minimum Cost to Hire K Workers.
• Regret with a heap - pass options, pay for the best one only when forced. Minimum Number of Refueling Stops.

Common mistakes

• Sorting by the wrong key: for the most non-overlapping intervals, sorting by start time fails where sorting by end time succeeds.
• Looping to n - 1 inclusive in Jump Game II, which counts an extra jump when you are already standing on the last index.
• One-pass Candy: a single sweep cannot see long decreasing runs; you need both directions and the max of the two.
• Comparators written as a[1] - b[1] overflow for large or negative values; use Integer.compare.
• In Gas Station, skipping the total-gas check and returning a start that cannot complete the loop.

All practice problems

8 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.