18 — Greedy

What greedy means

A greedy algorithm makes the locally best choice at each step and never reconsiders.

When it works it's simpler and faster than DP — no table, often O(n) and O(1) space. When it doesn't, it fails silently on inputs you won't think to test.

So the rule is:

Never claim greedy without an argument. The argument is the deliverable; the code is usually five lines.

The counterexample to keep loaded

Coin Change, coins = [1, 3, 4], amount = 6:

• Greedy (take the largest coin that fits): 4 + 1 + 1 = 3 coins.
• Optimal: 3 + 3 = 2 coins.

Greedy fails because taking the 4 forecloses the better pairing. This is the fastest way to justify "greedy is unsafe here, so I'll use DP" in conversation.

Proving a greedy choice

Two standard arguments. Have one ready before writing code.

1. The exchange argument

Take any optimal solution. Show that swapping in the greedy choice yields a solution that is no worse. Since this holds at every step, greedy is optimal.

Applied to Non-Overlapping Intervals (keep as many intervals as possible):

"I take the interval that ends earliest. Consider any optimal solution; its first interval ends no earlier than mine. So if I replace its first interval with mine, nothing breaks — my interval frees up at least as much room for everything after. Repeating this argument converts any optimal solution into the greedy one without loss. So greedy is optimal."

2. The invariant / reachability argument

Show the greedy quantity dominates whatever any solution could achieve.

Applied to Jump Game:

"I track the farthest index reachable so far. No strategy can pass a position that's unreachable from every earlier position. So if my running maximum stalls before the end, no solution exists — I'm not just failing, the problem is impossible."

When you can't produce either

Use DP. A DP solution that's one complexity tier slower still passes. A greedy solution that's wrong does not.

Say it out loud: "I can't convince myself the greedy choice is safe here — let me use DP, which is O(n · amount) and fits the constraints." That reads as judgement, not indecision.

Kadane's algorithm — Maximum Subarray

Find the contiguous subarray with the largest sum.

The greedy choice: discard the running prefix the moment it stops helping.

int best = nums[0], cur = nums[0];
for (int i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);      // restart here, or extend
    best = Math.max(best, cur);
}
return best;

Why discarding is safe:

"cur is the best sum of a subarray ending at i. If cur is negative, then any subarray extending through it would be strictly better without that prefix — dropping it adds a positive amount. So a negative prefix can never appear in an optimal answer, and I can discard it immediately."

Trace: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Answer: 6 ([4, -1, 2, 1]). ✓

Initialize with nums[0], not 0. An all-negative array must return its largest (least negative) element; starting at 0 wrongly returns 0. That's the standard bug and the standard edge case to raise.

Follow-up — return the indices: record start = i whenever you restart, and capture (start, i) whenever best improves.

Reachability greed

Jump Game — can you reach the end?

nums[i] is the maximum jump length from index i.

int farthest = 0;
for (int i = 0; i < nums.length; i++) {
    if (i > farthest) return false;                       // this index is unreachable
    farthest = Math.max(farthest, i + nums[i]);
}
return true;

Reading it: farthest is the furthest index reachable using everything seen so far. If the loop reaches an i beyond farthest, there's a gap nothing can cross.

Trace: nums = [3, 2, 1, 0, 4]

Correctly returns false — index 3 holds a 0, and nothing can jump past it. ✓

Jump Game II — the minimum number of jumps

This is BFS by levels, written without a queue.

int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {               // stop BEFORE the last index
    farthest = Math.max(farthest, i + nums[i]);
    if (i == curEnd) {                                    // exhausted the current level
        jumps++;
        curEnd = farthest;                                // the next level's boundary
    }
}
return jumps;

The BFS framing explains everything:

• curEnd = the last index reachable in jumps jumps — a BFS frontier.
• Walking i up to curEnd scans that entire level, computing how far the next level reaches.
• Hitting i == curEnd means the level is exhausted: take a jump, and the new frontier is farthest.

Describing it this way is far clearer than narrating the pointers.

i < nums.length - 1 stops before the last index. Otherwise arriving exactly at the end would trigger one spurious extra jump.

Gas Station

Stations in a circle; gas[i] available, cost[i] to reach the next. Find a starting index that completes the loop, or −1.

if (Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) return -1;   // feasibility

int start = 0, tank = 0;
for (int i = 0; i < gas.length; i++) {
    tank += gas[i] - cost[i];
    if (tank < 0) {                    // can't reach station i+1 from `start`
        start = i + 1;                 // ...and no station between start and i works either
        tank = 0;
    }
}
return start;

Two claims, both needed:

1. If total gas ≥ total cost, a solution exists. Guaranteed by the problem's structure — there's always a valid rotation.

2. If the tank goes negative between start and i, no station in [start, i] can be the answer.

Here's the argument, and it's what makes this O(n) instead of O(n²):

"Every station between start and i was reached with a non-negative tank. So starting fresh at any of them would give at most as much fuel arriving at i as the current run had — and the current run already failed. Therefore all of them fail too, and I can skip directly to i + 1."

Without that insight you'd retry every starting index separately.

Counting greed

Hand of Straights

Can the cards be divided into groups of groupSize consecutive values?

The forced move: the smallest remaining card must begin a group — nothing smaller exists to precede it. That forced move is what makes greed valid.

if (hand.length % groupSize != 0) return false;          // O(1) rejection

TreeMap<Integer, Integer> count = new TreeMap<>();
for (int c : hand) count.merge(c, 1, Integer::sum);

while (!count.isEmpty()) {
    int start = count.firstKey();                        // smallest remaining MUST lead
    for (int i = start; i < start + groupSize; i++) {
        Integer c = count.get(i);
        if (c == null) return false;                     // the run is broken
        if (c == 1) count.remove(i);
        else count.put(i, c - 1);
    }
}
return true;

TreeMap is used for firstKey() — O(log n) access to the smallest remaining value (02). A HashMap couldn't answer that.

Trace: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

Returns true. ✓

Partition Labels

Split a string so each letter appears in at most one part, making parts as small as possible.

The key fact: a part containing letter c must extend to c's last occurrence. So precompute the last index of every letter, then sweep.

int[] last = new int[26];
for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;   // final write wins

List<Integer> res = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
    end = Math.max(end, last[s.charAt(i) - 'a']);        // extend the boundary
    if (i == end) {                                      // every letter so far ends by here
        res.add(end - start + 1);
        start = i + 1;
    }
}
return res;

last[c] = i inside the first loop works because later writes overwrite earlier ones — so after the loop it holds the final occurrence.

Trace: s = "ababcbacadefegde" — last['a'] = 8, last['b'] = 5, last['c'] = 7, …

First part is "ababcbaca". ✓

The reusable pattern: precompute a per-element extent, then sweep. It recurs throughout interval problems (21).

Constraint-propagation greed

Merge Triplets to Form Target Triplet

Merging takes element-wise maxima. Can you reach target?

boolean[] found = new boolean[3];
for (int[] t : triplets) {
    if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;   // DISQUALIFIED
    for (int i = 0; i < 3; i++) if (t[i] == target[i]) found[i] = true;
}
return found[0] && found[1] && found[2];

Two-step reasoning:

1. Filter. Since merging takes maxima, any triplet exceeding the target in any position would push that position permanently too high. Such triplets are unusable — skip them.
2. Cover. Among the survivors, using more of them can never hurt (maxima only rise, and they're all capped at the target). So the question reduces to: does each position get hit exactly?

Valid Parenthesis String

* can be (, ), or empty. Is the string valid?

The insight: instead of committing to each *, track a RANGE of possible open counts.

int lo = 0, hi = 0;                     // min and max possible open parens
for (char c : s.toCharArray()) {
    if (c == '(')      { lo++; hi++; }
    else if (c == ')') { lo--; hi--; }
    else               { lo--; hi++; }  // '*' could be ')', '', or '('

    if (hi < 0) return false;           // too many closers even in the BEST case
    lo = Math.max(lo, 0);               // never let the minimum go negative
}
return lo == 0;                         // zero open parens must be ACHIEVABLE

Two subtleties worth stating:

lo = Math.max(lo, 0) — treating a * as ) when nothing is open isn't a legal choice, it's an impossible one. So clamp to 0 rather than tracking a meaningless negative.

hi < 0 is fatal but lo < 0 is not. hi is the most optimistic count; if even that is negative, there are genuinely too many closers. But lo going negative just means one particular interpretation failed — others remain.

The range formulation is exactly what lets you defer the decision about each * instead of branching. That's the whole trick.

Greedy in the other sections

Several problems filed elsewhere are greedy at heart. Recognizing the shared reasoning is worth more than the individual tricks:

• Intervals (21) — sort by end time, take the earliest-ending compatible interval.
• Task Scheduler (14) — always run the most frequent available task.
• Dijkstra / Prim (18) — always finalize the cheapest frontier node. These are greedy algorithms with proofs.
• Container With Most Water (07) — always move the shorter wall.

Recognition checklist

The last row is the important one. "Minimize a count" sounds greedy, and for arbitrary coin systems it is wrong.

Complexity summary