Algorithms
Greedy Local Optimum → Global Optimum
Make the best choice at each step. Never go back. If local decisions lead to a global optimum, greedy gives the simplest and fastest solution — often O(n log n) or O(n). The challenge isn't coding; it's proving correctness.
Foundations · Array · HashMap · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog. · Backtracking · Greedy · Patterns
01
Section One · Foundation
What is Greedy?
A greedy algorithm makes the locally optimal choice at each step and never revises it. It works when the problem has the "greedy choice property" — a locally optimal choice leads to a globally optimal solution. Unlike dynamic programming (which considers all subproblems before choosing), greedy commits immediately. Unlike backtracking (which explores and undoes), greedy never undoes. This makes greedy algorithms simple to code and fast to run (typically O(n log n) for the sort step + O(n) for the greedy scan). The hard part is correctness — proving that greedy works for a given problem. In interviews, the "exchange argument" suffices: show that swapping any non-greedy choice for the greedy choice never makes things worse.
Analogy: You're at a buffet with limited plate space. Greedy strategy: always pick the dish that gives you the most satisfaction per square inch of plate space. You never put a dish back. This works if each dish's value is independent. It fails if dishes taste better in combination (then you need DP to consider all combos).
02
Section Two · Mental Model
How It Thinks
The problem has "greedy choice property" — a local optimum leads to a global optimum
▶
You can commit to the best choice NOW without considering future consequences. No need for DP's "try all options" or backtracking's "undo."
Sort the input by the greedy criterion (end time, deadline, ratio, etc.)
▶
Sorting pre-arranges elements so the greedy scan always picks the right one first. Most greedy solutions are: sort → single pass. O(n log n) total.
The "exchange argument": swapping a non-greedy choice for the greedy choice never makes things worse
▶
This is how you prove greedy correctness in interviews. "Suppose we didn't pick the earliest-ending activity. The one we picked ends later, so we have LESS room for future activities — never better."
Greedy fails when future choices depend on current choices in complex ways
▶
Coin change with denominations {1, 3, 4}: greedy picks 4+1+1=3 coins for 6. DP finds 3+3=2 coins. When local optimum ≠ global optimum → use DP.
Many greedy problems pair with a heap for "best currently available"
▶
Meeting Rooms II: sort by start time, min-heap of end times. Task Scheduler: max-heap of frequencies. The heap dynamically tracks the greedy choice.
Greedy often appears disguised as "sort by X, scan once, track state"
▶
If you can solve a problem with sort + single pass + a few variables → it's greedy. If you need memoisation or a multi-dimensional dp table → it's DP.
03
Section Three · Greedy vs DP
When Greedy Works (and When It Doesn't)
| Aspect | Greedy | Dynamic Programming |
|---|---|---|
| Decision | Commit immediately, never revise | Consider all subproblems, pick best |
| Correctness | Exchange argument (harder to prove) | Optimal substructure (systematic) |
| Time | O(n log n) or O(n) typically | O(n²) or more typically |
| When it works | Local optimum = global optimum | Overlapping subproblems + optimal substructure |
| Coin change {1,5,10,25} | ✓ Greedy works (standard denom) | Also works (but slower) |
| Coin change {1,3,4} → 6 | ✗ Greedy: 4+1+1=3 coins | ✓ DP: 3+3=2 coins |
Interview heuristic:
- Try greedy first — it's faster and simpler. Test it with a small counterexample.
- If the greedy answer matches the optimal answer for all small cases you can think of, code it.
- If you find a counterexample, switch to DP.
- Many interviewers accept: "I suspect greedy works here because [exchange argument]. Let me verify with an example."
04
Section Four · Intervals
Interval Scheduling — The Classic Greedy
The interval scheduling maximisation problem: given n intervals, select the maximum number of non-overlapping intervals. The greedy strategy: sort by END time, greedily pick the earliest-ending interval that doesn't overlap with the last picked. This always works because picking the earliest-ending interval leaves the most room for future intervals (exchange argument).
Java — Non-overlapping Intervals (LC 435)
// Minimum intervals to REMOVE so the rest don't overlap // = total - maximum non-overlapping int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // sort by END int kept = 1, end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) { // no overlap
kept++;
end = intervals[i][1];
}
// else: skip (overlaps → remove this one)
}
return intervals.length - kept;
}
Sort by END time
Max Non-Overlapping
Pick earliest-ending. Skip if start < last end. Greedy picks: most activities, minimum removals.
Sort by START time
Merge Overlapping
Merge if current start ≤ prev end. Extend prev end. Use for Merge Intervals (LC 56).
05
Section Five · Jump Game
Jump Game — Reachability Greedy
Jump Game I (LC 55)
Can you reach the last index? nums[i] = max jump from index i.
Java
boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false; // can't reach index i
farthest = Math.max(farthest, i + nums[i]);
}
return true; // O(n)
}
Jump Game II (LC 45)
Minimum jumps to reach the last index.
Java — BFS-style greedy (levels = jumps)
int jump(int[] nums) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == curEnd) { // reached end of current level
jumps++;
curEnd = farthest; // next level boundary
}
}
return jumps; // O(n)
}
Jump Game II is BFS in disguise:
- Each "level" is the range of indices reachable with the current number of jumps.
curEnd= level boundary. farthest= how far the next level reaches. Increment jumps when you pass a level boundary.
06
Section Six · More Patterns
Common Greedy Patterns
| Pattern | Strategy | Example |
|---|---|---|
| Sort by end time | Pick earliest-ending, skip overlapping | Non-overlapping Intervals (LC 435) |
| Track farthest | At each index, update farthest reachable | Jump Game I & II (LC 55, 45) |
| Sort + heap | Sort by one criterion, heap tracks other | Meeting Rooms II (LC 253) |
| Balance + / − | Track running surplus, find start position | Gas Station (LC 134) |
| Greedy from both ends | Process from left and right, merge | Candy (LC 135) |
| Digit greedy | Build largest/smallest number digit-by-digit | Remove K Digits (LC 402) |
Java — Gas Station (LC 134)
int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int net = gas[i] - cost[i];
total += net;
tank += net;
if (tank < 0) { // can't reach i+1 from start
start = i + 1; // try next station
tank = 0; // reset tank
}
}
return total >= 0 ? start : -1; // O(n)
}
07
Section Seven · When to Use
Recognising Greedy Problems
| Signal | Greedy Strategy | Example |
|---|---|---|
| "maximum non-overlapping intervals" | Sort by end time, pick greedily | Non-overlapping Intervals (LC 435) |
| "minimum meeting rooms" | Sort by start, min-heap of end times | Meeting Rooms II (LC 253) |
| "can you reach the end" / "minimum jumps" | Track farthest reachable index | Jump Game I & II (LC 55, 45) |
| "gas station circuit" / "running surplus" | Track tank, reset when negative | Gas Station (LC 134) |
| "assign cookies" / "match capacity to demand" | Sort both, match smallest viable | Assign Cookies (LC 455) |
| "remove K digits for smallest number" | Monotonic stack, remove peaks | Remove K Digits (LC 402) |
08
Section Eight · Implementation
Build It Once
Build three greedy patterns: interval scheduling, jump game, and gas station. These cover the main families. Every other greedy problem is "sort + scan + simple state."
Greedy — Full Implementation
Java — Greedy patterns
import java.util.*;
public class GreedyPatterns {
// ═══ 1. Non-overlapping Intervals ═══════ O(n log n) static int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int kept = 1, end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
kept++;
end = intervals[i][1];
}
}
return intervals.length - kept;
}
// ═══ 2. Jump Game I ═════════════════════ O(n) static boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// ═══ 3. Jump Game II ════════════════════ O(n) static int jump(int[] nums) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == curEnd) {
jumps++;
curEnd = farthest;
}
}
return jumps;
}
// ═══ 4. Gas Station ═════════════════════ O(n) static int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int net = gas[i] - cost[i];
total += net;
tank += net;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
// ═══ 5. Merge Intervals ═════════════════ O(n log n) static int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
for (int[] iv : intervals) {
if (merged.isEmpty() || merged.getLast()[1] < iv[0])
merged.add(iv);
else
merged.getLast()[1] = Math.max(merged.getLast()[1], iv[1]);
}
return merged.toArray(new int[0][]);
}
// ═══ 6. Candy ═══════════════════════════ O(n) static int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
// left pass: higher rating than left neighbour → +1 for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i-1])
candies[i] = candies[i-1] + 1;
// right pass: higher rating than right neighbour → max for (int i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i+1])
candies[i] = Math.max(candies[i], candies[i+1] + 1);
int sum = 0;
for (int c : candies) sum += c;
return sum;
}
public static void main(String[] args) {
System.out.println(eraseOverlapIntervals(
new int[][]{{1,2},{2,3},{3,4},{1,3}})); // 1 System.out.println(canJump(
new int[]{2,3,1,1,4})); // true System.out.println(jump(
new int[]{2,3,1,1,4})); // 2 System.out.println(canCompleteCircuit(
new int[]{1,2,3,4,5},
new int[]{3,4,5,1,2})); // 3
}
}
Python — Greedy patterns
# ═══ 1. Non-overlapping Intervals ═══════ O(n log n) def erase_overlap(intervals):
intervals.sort(key=lambda x: x[1])
kept, end = 1, intervals[0][1]
for s, e in intervals[1:]:
if s >= end:
kept += 1
end = e
return len(intervals) - kept
# ═══ 2. Jump Game I ═════════════════════ O(n) def can_jump(nums):
farthest = 0
for i, v in enumerate(nums):
if i > farthest: return False
farthest = max(farthest, i + v)
return True # ═══ 3. Jump Game II ════════════════════ O(n) def jump(nums):
jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthest
return jumps
# ═══ 4. Gas Station ═════════════════════ O(n) def can_complete_circuit(gas, cost):
total = tank = start = 0
for i in range(len(gas)):
net = gas[i] - cost[i]
total += net
tank += net
if tank < 0:
start = i + 1
tank = 0
return start if total >= 0 else -1
# ═══ 5. Merge Intervals ═════════════════ O(n log n) def merge(intervals):
intervals.sort()
merged = [intervals[0]]
for s, e in intervals[1:]:
if s <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e])
return merged
# ═══ 6. Candy ═══════════════════════════ O(n) def candy(ratings):
n = len(ratings)
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)
# Demo
print(erase_overlap([[1,2],[2,3],[3,4],[1,3]])) # 1
print(can_jump([2,3,1,1,4])) # True
print(jump([2,3,1,1,4])) # 2
print(can_complete_circuit([1,2,3,4,5],[3,4,5,1,2])) # 3
09
Section Nine · Java Reference
Use It In Java
IN JAVA — Greedy Idioms
| Idiom | Code | When |
|---|---|---|
| Sort by end time | Arrays.sort(iv, (a,b) -> a[1] - b[1]); | Interval scheduling / removals |
| Sort by start time | Arrays.sort(iv, (a,b) -> a[0] - b[0]); | Merge intervals / meeting rooms |
| Track farthest | farthest = Math.max(farthest, i + nums[i]); | Jump game / reachability |
| Running surplus + reset | if (tank < 0) { start = i+1; tank = 0; } | Gas station / circular problems |
| Two-pass (L→R, R→L) | Left pass + right pass with Math.max | Candy / trapping rain water |
| Min-heap for "smallest available" | PriorityQueue<Integer> pq = new PriorityQueue<>(); | Meeting rooms, task scheduler |
⚠ Gotcha: When sorting
int[][] intervals, (a,b) -> a[1] - b[1] can overflow if values are near Integer.MAX_VALUE. Use Integer.compare(a[1], b[1]) for safety. In interviews, the subtraction form is fine for typical inputs.
⚠ Gotcha: "Sort by end time" and "sort by start time" solve DIFFERENT problems. End time → max non-overlapping. Start time → merge overlapping. Using the wrong sort order gives a wrong answer.
10
Section Ten · Practice
Problems To Solve
Greedy problems tend to be "aha" problems — the solution is simple once you see it, but hard to discover. Focus on understanding WHY greedy works (exchange argument) and learning to recognise the pattern (sort + scan). If you can't explain why greedy is correct, switch to DP.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | reachability | Jump Game — LC 55 | Track farthest reachable. If i > farthest → unreachable. O(n). |
| Medium | BFS-greedy | Jump Game II — LC 45 | BFS levels: track current range end and farthest. Increment jumps at level boundary. O(n). |
| Medium | intervals | Non-overlapping Intervals — LC 435 | Sort by end. Greedily keep earliest-ending. Remove count = total − kept. |
| Medium | intervals | Merge Intervals — LC 56 | Sort by start. Merge if current start ≤ prev end. |
| Medium | surplus | Gas Station — LC 134 | Total gas ≥ total cost → solution exists. Track running tank; reset on negative. |
| Hard | two-pass | Candy — LC 135 | Two-pass greedy: left-to-right ensures higher-rating-than-left gets more; right-to-left ensures higher-than-right; take max. |
Interview Pattern:
- See "interval scheduling / overlap" → sort by end, sweep. See "can you reach / minimum jumps" → track farthest.
- See "circular surplus" → running sum, reset on negative.
- Greedy is always: sort (optional) → single pass → a few variables.
- If you need a dp table or memoisation → it's not greedy.