Pattern 19: Greedy
Pattern guideUpdated
On this page
- 0. The Template (Copy-Paste Skeleton)
- Choosing the sort key — this table is the pattern
- The question you MUST answer before coding greedy
- Greedy vs DP — the discriminator
- Java gotchas
- 1. Pattern Identification & Logic
- How to Identify (Interview Triggers)
- When Greedy Works (the theory you must mention out loud)
- The Algorithm (template)
- The ‘Trick’ to Know
- 2. Java Implementation (Brute Force vs. Optimal)
- Example Problem: Jump Game — LC 55
- Example Problem: Non-overlapping Intervals — LC 435
- Java Architecture Insights
- 3. Mental Model & Visualization
- ASCII (activity selection — LC 435 / 452)
- Senior Mental Trigger
- 4. Curated Problem Lists
- Commonly Asked (Bread & Butter)
- FAANG ‘Aha!’ Level (Hard / Unintuitive)
- Frequency at MAANG (2026)
- 5. Time & Space Complexity Table
- 6. Greedy vs DP — when to switch
- 7. Interview Red Flags & Gotchas
- 8. Companion 90-second Pitch (verbal)
0. The Template (Copy-Paste Skeleton)
Greedy is almost always sort by the right key, then one linear sweep. Choosing the sort key is the problem; the sweep is four lines.
// TEMPLATE A — SORT + SWEEP (the canonical greedy shape)
int greedy(int[][] items) {
Arrays.sort(items, (a, b) -> Integer.compare(a[KEY], b[KEY])); // ← the whole decision
int result = 0, lastTaken = Integer.MIN_VALUE;
for (int[] item : items) {
if (isCompatible(item, lastTaken)) { // take it if it doesn't conflict
result++;
lastTaken = item[END];
}
}
return result;
}// TEMPLATE B — REACHABILITY SWEEP (jump games, gas station) — no sorting at all
int farthest = 0;
for (int i = 0; i < n; i++) {
if (i > farthest) return false; // this index is unreachable → stop
farthest = Math.max(farthest, i + nums[i]); // extend the reachable frontier
}
return true;// TEMPLATE C — GREEDY + HEAP (take the best available so far, revoke the worst later)
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap of what we've committed to
for (int[] task : tasksSortedByDeadline) {
heap.offer(task[PROFIT]);
if (heap.size() > capacity) heap.poll(); // drop the worst commitment — "regret" greedy
}Choosing the sort key — this table is the pattern
| Problem | Sort by | Why |
|---|---|---|
| Max non-overlapping intervals (LC 435) | end ascending | finishing earliest leaves the most room |
| Min arrows to burst balloons (LC 452) | end ascending | one arrow at the earliest end hits the most |
| Min meeting rooms (LC 253) | start + min-heap of ends | need concurrency, not selection |
| Merge intervals (LC 56) | start ascending | overlaps are adjacent once sorted |
| Task scheduler with deadlines (LC 630) | deadline ascending | + a max-heap to revoke the longest task |
| Fractional knapsack | value/weight descending | best density first |
| Gas station (LC 134) | no sort — single sweep | Template B |
| Jump game (LC 55, 45) | no sort — single sweep | Template B |
The question you MUST answer before coding greedy
“Why is the locally best choice also globally optimal?”
If you can’t justify it, greedy is probably wrong and you need DP. Two ways to justify:
- Exchange argument: take any optimal solution; show you can swap in your greedy choice without making it worse. (Earliest-finish-time: swapping in the earliest-ending interval never reduces how many fit afterwards.)
- Stays-ahead: show that after every step, greedy’s partial solution is at least as good as any other strategy’s.
Greedy vs DP — the discriminator
| Signal | Greedy | DP |
|---|---|---|
| One choice per step, never revisited | ✅ | |
| Choice depends on future subproblem results | ✅ | |
| Coin change with arbitrary denominations | ❌ (fails: coins=[1,3,4], amount=6 → greedy gives 3 coins, optimal is 2) |
✅ |
| Coin change with canonical currency (1,5,10,25) | ✅ | ✅ |
| “Maximum / minimum number of X you can select” | usually ✅ | |
| “Count the number of ways” | ❌ | ✅ |
Fastest sanity check: construct a counter-example in 60 seconds. If you can’t, greedy is probably safe. If you can, switch to DP and say why — that’s a strong signal either way.
Java gotchas
Arrays.sort(int[][], comparator)uses TimSort — O(n log n), stable. ButArrays.sort(int[])on primitives uses dual-pivot quicksort and takes no comparator.- Never
(a, b) -> a[0] - b[0]— overflows.Integer.compare(a[0], b[0]). - Sorting is usually the dominant cost: O(n log n) total even though the sweep is O(n).
1. Pattern Identification & Logic
How to Identify (Interview Triggers)
- “Maximum / minimum number of X” where each choice is local
- “Schedule as many meetings / jobs / intervals as possible”
- “Minimum number of jumps / refuels / coins / platforms”
- “Assign A to B to maximize/minimize Y”
- “Can you reach the end?” / “Can you complete the task?”
- A DP problem where you suspect the optimal substructure is always “pick the best now” — try greedy first; if it works, code is shorter and faster
- Problems with an obvious sort preprocessing step
- “Gas station circular tour”, “candy distribution”, “jump game”
When Greedy Works (the theory you must mention out loud)
Greedy is provably optimal only when the problem has BOTH:
- Greedy choice property — a global optimum can be reached by making locally optimal choices
- Optimal substructure — optimal solution contains optimal solutions to subproblems
If you can’t prove it, fall back to DP. Senior signal: explicitly say “I’ll try greedy. If I can’t justify why the local choice is always safe, I’ll switch to DP.”
The Algorithm (template)
Most greedy problems follow ONE of these three shapes:
SHAPE A — Sort then sweep:
sort(items, by some key) // start time, end time, ratio, deadline
for each item:
if compatible with previous choice:
take it
update state (e.g., last_end, current_sum, count)
SHAPE B — Single linear pass with running state:
state = initial
for each item:
choose action that maximizes/minimizes the local invariant
update state
return state
SHAPE C — Heap-based "always pick best available":
minHeap or maxHeap of candidates
while heap not empty:
pick top
update state
push new candidates exposed by the choiceThe ‘Trick’ to Know
- The sort key IS the algorithm. For interval problems, sorting by end time ⇒ activity selection (max meetings). Sorting by start time ⇒ merge intervals or min meeting rooms. Get the key right and the rest is 5 lines.
- Counter-example check: before committing to a greedy strategy, mentally construct a counter-example. If you can’t break it in 30 seconds, run with it. If you can, switch to DP.
- For two-pointer greedy (Container With Most Water, 3Sum closest): the invariant is “always move the pointer that can possibly improve the answer.”
2. Java Implementation (Brute Force vs. Optimal)
Example Problem: Jump Game — LC 55
Given
nums[i]= max jump from indexi, can you reach the last index?
Brute Force: DP / DFS — O(n²)
class Solution {
public boolean canJump(int[] nums) {
boolean[] reachable = new boolean[nums.length];
reachable[0] = true;
for (int i = 0; i < nums.length; i++) {
if (!reachable[i]) continue;
for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {
reachable[i + j] = true;
}
}
return reachable[nums.length - 1];
}
}Optimal: Greedy from the right — O(n)
class Solution {
public boolean canJump(int[] nums) {
int lastGood = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= lastGood) {
lastGood = i;
}
}
return lastGood == 0;
}
}Why greedy is correct here: if from position i you can reach a known-good position j, then i is also good. We don’t care how you reach the end — only whether. Local choice is safe.
Alternative greedy (forward pass — also O(n)):
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}Example Problem: Non-overlapping Intervals — LC 435
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // sort by END
int kept = 0;
int lastEnd = Integer.MIN_VALUE;
for (int[] it : intervals) {
if (it[0] >= lastEnd) { // compatible with previously kept
kept++;
lastEnd = it[1];
}
}
return intervals.length - kept;
}
}Why end-time sort works: of all intervals that overlap, keeping the one that ends first leaves maximum room for future picks. This is the classical “activity selection” proof.
Java Architecture Insights
Arrays.sort(arr, comparator)forint[][]— only works on object arrays, henceInteger.compare(a[1], b[1]). Forint[], no custom comparator; you’d convert or use streams.- Avoid
a[1] - b[1]— overflow risk on large ints. UseInteger.compareorLong.compare. - For heap-based greedy (LC 253, LC 1834):
PriorityQueueis min-heap by default; for max-heap passComparator.reverseOrder(). Comparator.comparingInt(...)is the most readable form in modern Java — prefer it for senior signal.
3. Mental Model & Visualization
ASCII (activity selection — LC 435 / 452)
intervals (sorted by END):
|
[1, 3] ------- |
[2, 4] ---- |
[3, 6] ---- | ← keep (1,3), skip (2,4) overlap
[5, 7] | ← keep (3,6), skip (5,7) overlap with 5<6? no — actually 5<6 overlap
...
Algorithm: sweep left-to-right, keep if start >= last_endSenior Mental Trigger
“Greedy = pick local optimum, can it always be proven safe? If yes, O(n) or O(n log n) with a sort. If you can’t prove it, escalate to DP.”
4. Curated Problem Lists
Commonly Asked (Bread & Butter)
| # | Problem | Difficulty | Greedy strategy |
|---|---|---|---|
| LC 55 | Jump Game | Medium | Track max reachable index |
| LC 45 | Jump Game II | Medium | BFS-style “expand current frontier” |
| LC 121 | Best Time to Buy and Sell Stock | Easy | Track min price seen so far |
| LC 122 | Best Time to Buy and Sell Stock II | Medium | Sum all positive deltas |
| LC 53 | Maximum Subarray (Kadane’s) | Medium | Reset running sum when it goes negative |
| LC 435 | Non-overlapping Intervals | Medium | Sort by end time, keep compatible |
| LC 452 | Min Arrows to Burst Balloons | Medium | Sort by end time, count distinct shots |
| LC 56 | Merge Intervals | Medium | Sort by start, merge if overlap |
| LC 763 | Partition Labels | Medium | Track last-seen index of each char |
FAANG ‘Aha!’ Level (Hard / Unintuitive)
| # | Problem | Difficulty | Greedy strategy |
|---|---|---|---|
| LC 134 | Gas Station | Medium | If total_gas ≥ total_cost, answer exists; single pass tracks restart point |
| LC 135 | Candy | Hard | Two passes (L→R then R→L), take max |
| LC 253 | Meeting Rooms II | Medium | Min-heap of end times |
| LC 1024 | Video Stitching | Medium | Sort by start, extend reach greedily |
| LC 871 | Minimum Refueling Stops | Hard | Max-heap of fuel passed so far |
| LC 502 | IPO | Hard | Two heaps — affordable projects + max profit |
| LC 630 | Course Schedule III | Hard | Sort by deadline, max-heap of durations |
| LC 621 | Task Scheduler | Medium | Count frequencies, idle slots formula |
| LC 406 | Queue Reconstruction by Height | Medium | Sort by (height desc, k asc), insert at k |
| LC 1326 | Minimum Taps to Open to Water a Garden | Hard | Convert to interval cover, jump-game II |
| LC 678 | Valid Parenthesis String | Medium | Track min/max possible open count |
Frequency at MAANG (2026)
| Pattern usage | Amazon | Meta | Apple | Netflix | |
|---|---|---|---|---|---|
| Greedy | ★★ | ★★ | ★★ | ★ | ★ |
Greedy + intervals (LC 56, 435, 253) is a near-guaranteed appearance at Meta and Google.
5. Time & Space Complexity Table
| Approach | Time | Space | Notes |
|---|---|---|---|
| Sort + linear sweep | O(n log n) | O(1)–O(n) | Most common shape |
| Single pass | O(n) | O(1) | Kadane, Jump Game, Gas Station |
| Heap-based greedy | O(n log n) | O(n) | Meeting Rooms II, IPO, Refueling Stops |
| Two-pointer greedy | O(n) | O(1) | Container With Most Water |
6. Greedy vs DP — when to switch
| Symptom | Greedy works? | Switch to |
|---|---|---|
| Choice now changes the set of future choices, not just count | ❌ Often no | DP |
| Counter-example found in 30s | ❌ No | DP |
| Sorting reveals a clean ordering | ✅ Likely yes | Stay greedy |
| Problem reads like “max number of …” with constraints | ✅ Try greedy first | Stay greedy |
| “Min cost to do X” with overlapping subproblems | ❌ Usually no | DP |
| LC 322 Coin Change (general coins) | ❌ Greedy fails on {1,3,4,5} pick 7 | DP |
| LC 860 Lemonade Change (only $5/10/20) | ✅ Always give biggest bill | Greedy |
Coin Change is the canonical greedy-fails example. Memorize the counter-example: coins {1, 3, 4}, target 6. Greedy says 4+1+1 = 3 coins; optimal is 3+3 = 2 coins.
7. Interview Red Flags & Gotchas
- ❌ Jumping into code without justifying why local choice is safe — interviewer will ask “prove it” and you’ll fumble
- ❌ Sorting by the wrong key —
startvsendmatters more than you’d think (LC 435 needs end; LC 56 needs start) - ❌ Using
a[1] - b[1]comparator (overflow) — useInteger.compare - ❌ Confusing “Merge Intervals” (LC 56) with “Non-overlap” (LC 435) — different sort keys, different sweep
- ❌ Going greedy on Coin Change / Knapsack / Longest Increasing Subsequence — these are DP, not greedy
- ❌ Missing the heap variant — when “always pick the best available so far” appears, default to PriorityQueue
- ❌ Forgetting edge cases: empty input, single element, all same value, negative values (Kadane handles them; many naive greedies don’t)
8. Companion 90-second Pitch (verbal)
“When I see a ‘max/min count’ or ‘schedule X’ problem, I try greedy first. Two things have to hold: optimal substructure and the greedy-choice property — the local pick must be provably safe. If I can construct a counter-example, I escalate to DP. For interval problems, the sort key is the algorithm: end-time sort gives activity selection, start-time sort gives merge intervals or meeting rooms. For ‘pick the best available’ problems, I use a heap. The wins are usually O(n) or O(n log n) with O(1) extra space — much tighter than DP.”
A clean opener for LC 55 / 435 / 253 / 134 / 763 and the whole greedy family.