Greedy
8 questions. The shortest code in the entire set, and the hardest to justify.
Never claim greedy without an argument. The argument is the deliverable; the code is usually five lines.
The counterexample to keep loaded
Coins {1, 3, 4}, amount 6: greedy takes 4 + 1 + 1 = 3 coins, the optimum is 3 + 3 = 2. The greedy step is locally optimal at every turn and globally wrong. Name this the moment an interviewer asks "can't you just be greedy?" about something that needs DP.
Three kinds of justification
Every question here uses one of these, and knowing which one you're using is most of the interview.
| Argument | Shape | Questions |
|---|---|---|
| Exchange | Any optimal solution can be rewritten to use my choice, no worse | 8 (prefer ( over *) |
| Reachability / exactness | I'm not choosing — I'm computing the exact frontier | 2, 3, 8 |
| Forced move | There is only one legal option, so no optimality proof is needed | 5 |
| Monotone and capped | Adding more can only help and can never overshoot | 6 |
| Block elimination | One failure kills a whole range of candidates | 1, 4 |
The strongest position is the forced move (Q5): the smallest remaining card must start its group, so there is nothing to prove beyond legality. The weakest is a bare exchange argument — which is why Q8's is the only one in the set.
The two problems where a plausible greedy is wrong
Jump Game II — "each jump goes as far as it can" fails, because the furthest landing spot may have the worst onward reach.
Measured: wrong on 233 of 4,000 random arrays — about 6%, the frequency that survives casual testing and fails in production.
Merge Triplets — checking coverage before disqualification looks harmless because LeetCode's own negative example returns false either way. On [[2,2,5],[1,1,2]] against target [2,2,2] it flips the answer to true.
Discarding a prefix: the same argument twice
Kadane (Q1) drops the running sum when it turns negative. The test nums[i] > cur + nums[i] simplifies to cur < 0 — only the sign matters, never the length.
Gas Station (Q4) resets the start when the tank goes negative — and skips every candidate in between, because each was reached with a non-negative prefix and would arrive with even less. Same reasoning, applied to feasibility rather than optimisation, and it's what turns O(n²) into one pass.
Deferring a decision instead of making one
Valid Parenthesis String (Q8) never decides what a * means. The set of reachable open-counts is always a contiguous interval, so [lo, hi] replaces 3^n branches — with two deliberately asymmetric guards: hi < 0 is fatal, lo < 0 is clamped.
Several of these aren't really greedy
Worth being honest about, because the label misleads:
- Jump Game / Jump Game II compute an exact reachability frontier. Nothing is chosen, so nothing needs to be proved optimal — only that the frontier is exact.
- Valid Parenthesis String computes the exact reachable set. Same situation.
- Hand of Straights has no choice at all at any step.
The genuine greedy choices — where a different choice was available and had to be ruled out — are Kadane's discard, Gas Station's reset, and Q8's preference for ( over * in the stack formulation.
Complexity
| Question | Time | Space |
|---|---|---|
| Maximum Subarray | O(n) | O(1) |
| Jump Game | O(n) | O(1) |
| Jump Game II | O(n) | O(1) |
| Gas Station | O(n) | O(1) |
| Hand of Straights | O(n log n) | O(n) |
| Merge Triplets | O(n) | O(1) |
| Partition Labels | O(n) | O(1) — int[26] |
| Valid Parenthesis String | O(n) | O(1) |
Seven of the eight are O(n) / O(1). Hand of Straights needs the sorting bound because adjacency is order information.
The traps
| Trap | Symptom |
|---|---|
Seeding Kadane's best at 0 (Q1) | All-negative input returns 0 — wrong on 4,000/4,000 |
Updating best before cur (Q1) | Wrong on 1,365/4,000; [-2,5] returns −2 |
| Extending the frontier before the reachability check (Q2) | [1, 0, 5] returns true |
Looping to n-1 instead of n-2 (Q3) | [2,3,1,1,4] returns 3, not 2 |
| Hopping as far as each jump allows (Q3) | Wrong on 233/4,000 |
Merging total and tank into one variable (Q4) | gas=[2,3,4], cost=[3,4,3] returns 2 instead of −1 |
int have = count.get(c) (Q5) | NPE on an absent key |
| Checking coverage before disqualification (Q6) | [[2,2,5],[1,1,2]] / [2,2,2] returns true |
Building last[] in a reverse loop (Q7) | Silently records first occurrences |
Not clamping lo at 0 (Q8) | "(*)" returns false |
Testing hi == 0 at the end (Q8) | Demands every interpretation balance; "(*)" returns false |
Verification
Every snippet compiled and cross-checked against an independent implementation — 30,000+ randomized cases:
- Q1 across Kadane, prefix sums, divide-and-conquer and the returned window, all against
O(n²)brute force - Q2 forwards, backwards and DP against exhaustive DFS
- Q3 greedy, explicit windows and DP against BFS shortest path
- Q4 against try-every-start, plus the greedy's start index compared to the smallest valid one on 212,882 feasible inputs
- Q5 against a backtracker that tries every present value as a group start — confirming the forced move misses nothing
- Q6 against all
2^nsubsets - Q7 against a disjoint-charset cut scan, with "sizes sum to
n" asserted every time - Q8 across the interval method and two index stacks, against exhaustive
3^nexpansion
Separately, every numeric claim in the prose and in all five diagrams is recomputed by a harness — 97 assertions covering worked examples, traces, measured failure rates and diagram cell values. Two of my own claims were wrong and were corrected by it:
- I asserted that LeetCode's negative example for Q6 punishes checking coverage before the filter. It doesn't — it returns false either way.
[[2,2,5],[1,1,2]]against[2,2,2]is the smallest input that actually flips. - I listed
"(*()"as invalid for Q8. Reading the star as)gives"()()", so it is valid.