Greedy
Why greedy exists — the story
You're an intern at a scheduling startup. The founder walks up: "Given a list of meeting requests with start and end times, what's the maximum number of non-overlapping meetings I can pack into one conference room?"
The obvious approach: try every subset of meetings. Check each for validity (no overlaps). Return the largest valid subset. There are 2ⁿ subsets — for n = 30 meetings, that's 10⁹ combinations. Your laptop chokes for a minute, then returns the right answer. It's correct. It's provably optimal. And for n ≤ 20 it's actually a legit answer that many textbooks use as their reference for scheduling problems.
But at n = 100 meetings (a large enterprise's daily calendar), brute force is 10³⁰ subsets — more than the age of the universe in nanoseconds. And the killer insight is: you don't need to try every subset. You just need to answer "which meeting should I pick next?" at each step. If you always pick the meeting that ends earliest among all still-available meetings, you provably get the maximum count. Sort by end time, sweep left to right, greedily pick any meeting that doesn't overlap the last picked. O(n log n). For 100 meetings, that's ~700 ops — a microsecond. From universe-age to microsecond, by making the right local choice.
That's greedy: grab the best-looking option right now and never look back. When it works, the code is embarrassingly short (usually just sort, then sweep once). The catch is that "best right now" isn't always "best overall," so a greedy algorithm is only correct when two properties hold: the greedy-choice property (a locally optimal pick is safe to commit to) and optimal substructure (what's left is a smaller version of the same problem). In an interview the code is the easy part; the points come from proving it — most often with an exchange argument, where you show that any optimal solution can be nudged, one swap at a time, into the greedy one without ever getting worse.
A brute-force solution usually enumerates choices, schedules, subsets, or paths and then picks the best valid one. Can we do better? Only when a local choice can be proved safe. The rest of the chapter is about finding that proof: farthest reach, earliest finish, minimum prefix balance, or a frequency frame.
Before coding greedy, find the sort key that makes the safe choice obvious (earliest finish, largest ratio, nearest deadline). If you can construct a counterexample to "always take the locally best," greedy is wrong → switch to DP.
Greedy Coin Change — when it works, and when it doesn't
Greedy = "always take the biggest coin that fits." Sometimes optimal, sometimes not. Pick a coin set and target; watch greedy trace vs. the DP-optimal answer.
When to use it — local choices with a proof
Recognize by
- "fewest / smallest / earliest" with a locally safe choice
- sort-then-sweep problems — activity selection, interval scheduling, non-overlapping intervals
- "jump game" family, "gas station" — verify total feasibility, commit to the earliest reset
When NOT to use it
A locally-best choice can be regretted later — construct a counterexample ("if I take the largest coin first…") and if you find one, switch to Dynamic Programming. The exchange-argument proof is what separates a safe greedy from a wrong one.
History — Kruskal 1956, matroid theory 1935
Greedy algorithms as a formal class date to Joseph Kruskal's 1956 minimum-spanning-tree paper "On the shortest spanning subtree of a graph and the traveling salesman problem" (Proc. AMS 7(1):48-50). Kruskal proved that sorting edges by weight and greedily adding the cheapest cross-component edge produces a globally-optimal MST. The proof used what we now call an exchange argument — if the greedy answer differs from any optimal answer, you can swap one edge to reduce the difference without increasing the total weight, contradicting optimality.
The mathematical foundation is even older. Hassler Whitney's 1935 paper "On the abstract properties of linear dependence" introduced matroids — the abstract structure in which greedy always works. A matroid is a set system where "independence" satisfies specific axioms; when your problem is a matroid, the greedy algorithm provably finds the optimal answer. Kruskal's MST and Prim-Jarnik's MST are both matroid-greedy in this sense. Job Sequencing with Deadlines, Activity Selection, and Huffman Coding are also matroid-greedy problems.
Real-world adoption:
- Huffman Coding (1952) — the greedy compression algorithm inside every ZIP, PNG, JPEG, MP3, and MPEG file. Powered gzip, brotli, and Zstandard.
- Dijkstra's shortest-path algorithm (1959) — technically greedy (extract-min from priority queue). Used in every road-routing GPS, every internet routing protocol (OSPF, IS-IS), every network flow analysis.
- Kruskal's MST — cell tower placement, Internet backbone design, cluster analysis in bioinformatics, image segmentation.
- Prim's MST — the actual algorithm most textbook implementations use.
- Interval scheduling (earliest-finish-first) — every meeting-room scheduler, every "book the maximum non-overlapping X" application.
- Fractional Knapsack — CPU scheduling in real-time systems, resource allocation in cloud auto-scalers.
- Set Cover approximation — every anti-spam filter's rule-selection subsystem.
When you tell an interviewer "I'll prove correctness with an exchange argument," you're citing Kruskal's 1956 proof technique — still the gold standard for greedy-algorithm proofs 70 years later.
Canonical problem walkthrough — Jump Game II
Problem (↗ LeetCode): Given an array of non-negative integers nums, you are initially at index 0. Each element nums[i] is the maximum jump length from position i. Return the minimum number of jumps to reach the last index. Assume you can always reach the last index.
Approach 1 — Brute force recursion
From index 0, try every possible jump length. Return 1 + min(recursions from each landing).
int jumpBrute(int[] nums) {
return dfs(nums, 0);
}
int dfs(int[] nums, int i) {
if (i >= nums.length - 1) return 0;
int best = Integer.MAX_VALUE;
for (int step = 1; step <= nums[i]; step++) {
int sub = dfs(nums, i + step);
if (sub != Integer.MAX_VALUE) best = Math.min(best, sub + 1);
}
return best;
}Complexity: O(k^n) where k = max value. Exponential blowup for n > 20. Useful as a mental reference for "we're minimizing jumps."
Approach 2 — Dynamic programming
Bottom-up: dp[i] = minimum jumps to reach the last index from position i. Base case: dp[n-1] = 0. Fill from right to left.
int jumpDP(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
for (int step = 1; step <= nums[i] && i + step < n; step++) {
if (dp[i + step] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i + step] + 1);
}
}
}
return dp[0];
}Complexity: O(n²) time, O(n) space. For n = 10⁴, that's 10⁸ ops — passes but at the edge. Correct, but does more work than needed.
Approach 3 — Farthest-reach greedy (the interview answer)
The insight: at any position, the best "next jump" is the one that reaches the farthest. Track two pointers:
currentEnd: the farthest index reachable with the current number of jumpsfarthest: the farthest index reachable using one more jump from anywhere in[current position, currentEnd]
When i == currentEnd, we must commit to a new jump: increment count, set currentEnd = farthest.
int jump(int[] nums) {
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < nums.length - 1; i++) { // don't iterate past last index
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) { // must jump now
jumps++;
currentEnd = farthest;
if (currentEnd >= nums.length - 1) break; // reached the end
}
}
return jumps;
}Complexity: O(n) time, O(1) space. For n = 10⁴, ~10⁴ ops — trivially fast.
Why is greedy correct here? Exchange argument: suppose some optimal solution jumps to j at step k, and greedy jumps to g at step k with g > j. Any subsequent optimal jump from j reaches some position p. Since g > j and greedy's next-step farthest depends on positions in [current, g] ⊇ [current, j], greedy can reach p (or farther) in the same number of steps. Swap j → g in optimal; still optimal. Repeat: optimal converges to greedy.
Interview commentary:
- "DP is O(n²). We can do O(n) with greedy."
- "At every position, track the farthest we can reach with one more jump. When we exhaust the current jump's range, commit to another jump."
- "Correctness proof: exchange argument. Any position optimal can reach in k jumps, greedy can also reach in k jumps because greedy's next range dominates optimal's."
- "Loop bound is
n-1because we never land jumping from the last index."
Complexity ladder
| Approach | Time | Space | When |
|---|---|---|---|
| Recursion | O(k^n) | O(n) | Reference / n ≤ 20 |
| DP | O(n²) | O(n) | Correct but O(n²) at edge of TLE |
| Farthest-reach greedy | O(n) | O(1) | Interview default |
Jump Game II (Farthest-Reach Greedy) Medium
Problem
Each nums[i] is the max jump length from index i. Find the fewest jumps to reach the last index (reaching the end is always possible).
Constraints: 1 ≤ n ≤ 10⁴; 0 ≤ nums[i] ≤ 1000.
Example 1: [2,3,1,1,4] → 2 (jump 0→1→4).
Example 2: [2,3,0,1,4] → 2 (jump 0→1→4).
Solution — brute force
Brute force models each index as a node and explores every reachable next index to find the shortest path to the end. A plain recursive search can be exponential because it branches over all jump lengths; BFS is O(n²) in the worst case if every index reaches many later indices. The optimized greedy scan compresses BFS levels into two integers: the current frontier and the farthest next frontier.
queue = [0]
steps = 0
while queue is not empty:
pop every index in the current BFS layer
push every reachable next index not seen before
if the last index is reached, return steps + 1Brute force complexity: naive BFS can examine O(n²) edges; recursive enumeration can be exponential.
Solution — optimized
BFS-like level expansion: from the current reachable range, jump to the farthest reachable next.
curEnd is the boundary of positions reachable in jumps steps; farthest is the boundary reachable in jumps+1. When i hits curEnd, one more jump is forced.
Java
int jump(int[] a) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i < a.length - 1; i++) {
farthest = Math.max(farthest, i + a[i]);
if (i == curEnd) { jumps++; curEnd = farthest; }
}
return jumps;
}[2,3,1,1,4]. From index 0 (reach 2) the best next hop is index 1 (which reaches index 4). Two jumps 0→1→4 → answer 2.
"I first confirm identical tasks need at least n intervals between runs and idle slots are allowed. I start with brute force by enumerating or simulating possible schedules, which is exponential if I search all valid orders. I optimize by counting frequencies and using the max-frequency frame formula, giving O(tasks + A) time and O(A) space for alphabet size A."
Time Complexity
Time O(n). Each index before the last is scanned once while updating the farthest reachable boundary.
Space Complexity
Space O(1). The greedy scan keeps only jumps, curEnd, and farthest.
Learning notes
- Why loop only to
a.length - 1? — you do not need to jump after reaching the last index. - Why update
farthestevery index? — it records the best next frontier from the current BFS layer. - Why increment only at
i == curEnd? — that is where the current jump range is exhausted. - Why set
curEnd = farthest? — the next jump can cover exactly the farthest range discovered so far. - Why not choose a concrete next index? — only the frontier matters for the minimum jump count.
- Why greedy works? — farther reach dominates shorter choices within the same layer.
"I first confirm the end is reachable and I need the minimum number of jumps. I start with brute force DFS or BFS over all jumps, which can be exponential for DFS or O(n²) for naive BFS. I optimize by tracking the current level boundary and farthest next reach in one pass, giving O(n) time and O(1) space."
Each "level" is the set of indices reachable with the same number of jumps; taking the farthest reach is provably optimal because it dominates every other choice's future reach.
Counting jumps at every step instead of at the frontier. Example: nums=[2,3,1,1,4]. Incrementing jumps at each index gives 5; incrementing only when i == currentEnd (frontier boundary) gives 2. Update currentEnd = farthest and jumps++ together.
This is BFS on an implicit graph collapsed to O(n). Jump Game I (reachability) is an even simpler farthest-reach scan.
Same pattern, new tweaks
"Track the farthest you can reach from the current level" is a greedy BFS in disguise:
| Variation | The one thing that changes | Time |
|---|---|---|
| Jump Game I | just track the farthest reachable index; return whether it reaches the end | — |
| Jump Game III | actual BFS/DFS since you can jump both directions by arr[i] | — |
| Video Stitching / Minimum Number of Taps | the same "cover the line in fewest intervals" farthest-reach greedy | — |
| Minimum Number of Arrows | the interval-cover cousin (sort by end) | — |
Gas Station (Prefix-Balance Greedy) Medium
Problem
Around a circular route, station i provides gas[i] and it costs cost[i] to drive to the next station. Return the starting index from which you can complete the whole loop (or -1). A unique answer exists whenever total gas ≥ total cost.
Constraints: 1 ≤ n ≤ 10⁵; values ≥ 0.
Example 1: gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3.
Example 2: gas = [2,3,4], cost = [3,4,3] → -1 because total gas is insufficient.
Solution — brute force
Brute force tries every station as a start and simulates a full circuit while tracking tank balance. That is O(n²) time and O(1) space, and it repeats the same failing prefixes over and over. The optimized greedy scan uses the fact that if a candidate start fails at station i, every start inside that failed segment also fails, so the next candidate is i + 1 after a global total check.
for each station start:
tank = 0
for n legs around the circle:
tank += gas[i] - cost[i]
if tank < 0: fail this start
if all legs succeed: return start
return -1Brute force complexity: O(n²) time and O(1) extra space.
Solution — optimized
If total gas ≥ total cost, a unique start exists; it's just after the point of minimum running balance.
If you run out of gas going from start to i, no station in [start, i] can be the answer (each had ≤ 0 surplus to offer) → restart at i+1. Total feasibility is a separate global check.
tank is the surplus since the current candidate start; the moment it goes negative, every earlier candidate is eliminated.
Java
int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) { start = i + 1; tank = 0; } // reset candidate
}
return total >= 0 ? start : -1;
}gas=[1,2,3,4,5], cost=[3,4,5,1,2]. Running balance bottoms out entering index 3, so start at 3: 4→5→1→2→3 never dips below zero.
Time Complexity
Time O(n). One pass computes total surplus and eliminates invalid start ranges.
Space Complexity
Space O(1). Only total, tank, and start are stored.
Learning notes
- Why keep
total? — it proves whether any solution exists globally. - Why keep
tankseparately? — it measures surplus from the current candidate start only. - Why reset when
tank < 0? — every station in that failed segment is impossible. - Why set
start = i + 1? — the next station is the first candidate not disproved by the deficit. - Why reset
tank = 0? — the new candidate starts with an empty local balance. - Why return
startonly iftotal >= 0? — local recovery cannot fix global shortage.
"I first confirm the route is circular and returning any valid start is enough when total gas can cover total cost. I start with brute force by simulating the full loop from every station, which is O(n²) time and O(1) space. I optimize by resetting the candidate after any negative tank and checking total surplus, giving O(n) time and O(1) space."
Skipping the total check. Example: gas=[1,2,3,4], cost=[2,3,4,5]. Total gas 10 < total cost 14, so no station works — but a local reset can look promising. Verify sum(gas) >= sum(cost); if not, return -1.
"Reset the start when the running sum dips" mirrors Kadane's max-subarray reset — both discard a prefix that can only hurt.
Same pattern, new tweaks
"A running tally you reset the moment a prefix can only hurt" recurs across greedy scans:
| Variation | The one thing that changes | Time |
|---|---|---|
| Maximum Subarray (Kadane) | reset the running sum to 0 whenever it goes negative | — |
| Best Time to Buy and Sell Stock | track the min price so far and the best profit against it | — |
| Gas Station | reset the start to i+1 when the tank dips below 0, with a global feasibility gate | — |
Task Scheduler / Activity Selection (Sort-Driven Greedy) Medium
Problem
Given task labels and a cooldown n (identical tasks must be at least n apart), find the minimum number of intervals (including idle slots) to run every task.
Constraints: 1 ≤ tasks ≤ 10⁴; labels A–Z; 0 ≤ n ≤ 100.
Example 1: ["A","A","A","B","B","B"], n = 2 → 8 (AB_AB_AB).
Example 2: tasks = ["A","A","A","B","B","B"], n = 0 → 6 because no cooldown gaps are needed.
Solution — brute force
For task scheduling, brute force can simulate each time slot by repeatedly choosing an available task and trying schedules with idle slots when blocked. That search branches heavily and is effectively exponential if you enumerate orders; even a priority-queue simulation is more machinery than needed. The optimized formula observes that the most frequent task creates the idle-frame skeleton, then fills gaps with all other tasks in linear time over the task counts.
try every ordering of the tasks:
insert idle slots whenever a repeated label is too close
keep the shortest valid timeline
return the best lengthBrute force complexity: exponential if schedules are enumerated; simulation alternatives are usually O(T log A).
Solution — optimized
Activity selection — to fit the most non-overlapping intervals, sort by earliest finish time and greedily take any activity starting after the last taken finish. Exchange argument: swapping in the earliest-finishing compatible activity never reduces the count.
Task Scheduler (cooldown n between equal tasks) — the most frequent task dictates the skeleton: (maxFreq−1)·(n+1) + (#tasks with maxFreq), floored by total tasks.
Java
int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char task : tasks) freq[task - 'A']++;
int maxFreq = 0, maxCount = 0;
for (int f : freq) {
if (f > maxFreq) { maxFreq = f; maxCount = 1; }
else if (f == maxFreq) maxCount++;
}
int frame = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(tasks.length, frame);
}Greedy interval problems almost always sort by finish time (maximize count) or start time (merge/coverage). Choosing the wrong key is the classic greedy failure.
Earliest-finish selection underlies Non-overlapping Intervals (min removals) and Minimum Arrows to Burst Balloons (max non-overlap = min points).
tasks AAABBB, n=2. The three As frame the timeline A??A??A; Bs and idles fill the gaps → AB_AB_AB = 8 intervals.
Time Complexity
Time O(T + A), where T is the task count and A is the alphabet size. Counting dominates for fixed uppercase labels.
Space Complexity
Space O(A) for the frequency table.
Learning notes
- Why count frequencies? — only the most frequent labels determine unavoidable idle frames.
- Why use
maxFreq - 1blocks? — the last copy of the most frequent task does not need a following cooldown frame. - Why multiply by
n + 1? — each internal block holds one anchor task plus n cooldown positions. - Why add
maxCount? — all labels tied for maximum frequency occupy the final block. - Why
Math.max(tasks.length, frame)? — other tasks can fill idles, but the answer can never be shorter than the task count. - Why earliest-finish for activity selection? — finishing sooner leaves the most room for future compatible intervals.
When greedy fails → DP
What & why: the tell-tale signs that a locally optimal choice is not globally safe. Goal — decide fast between a greedy one-pass and a DP, and back the call with a counterexample or an exchange argument.
Coin Change with arbitrary denominations breaks greedy (largest-coin-first fails for coins {1,3,4}, amount 6: greedy 4+1+1=3 coins vs optimal 3+3=2). 0/1 Knapsack breaks greedy (value/weight ratio is optimal only for the fractional version). The tell: a locally best choice can foreclose a better global combination.
Greedy is safe iff you can prove the exchange argument. No proof, construct a small counterexample; if one exists, the problem is DP.
Non-overlapping Intervals (Interval Scheduling) Medium
↗ LeetCode: Non-overlapping Intervals
Problem
Find the minimum number of intervals to remove so the remaining ones don't overlap.
Constraints: 1 ≤ n ≤ 10⁵; start < end.
Example 1: [[1,2],[2,3],[3,4],[1,3]] → 1 (remove [1,3]).
Example 2: [[1,2],[1,2],[1,2]] → 2 (keep one interval, remove two).
Solution — brute force
Brute force tries subsets of intervals, checks which subsets are pairwise non-overlapping, and keeps the largest valid subset; removals are n - kept. That is exponential time and O(n) recursion space, so it is a correctness baseline only. The greedy optimization sorts by end time and always keeps the compatible interval that finishes earliest, because that leaves maximum room for all future intervals.
bestKept = 0
for each subset of intervals:
if every pair in the subset is non-overlapping:
bestKept = max(bestKept, subset size)
return n - bestKeptBrute force complexity: O(2^n · n²) time to enumerate and validate subsets.
Solution — optimized
Sort by end; greedily keep the earliest-finishing interval; count removals of those that overlap the last kept.
Keeping the earliest-ending compatible interval leaves the most room for the rest (exchange argument).
Java
int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // by end
int end = Integer.MIN_VALUE, removed = 0;
for (int[] iv : intervals) {
if (iv[0] >= end) end = iv[1]; // keep (compatible)
else removed++; // overlaps -> remove this one
}
return removed;
}[[1,2],[2,3],[3,4],[1,3]]. Keeping earliest-finishers [1,2],[2,3],[3,4] forces dropping [1,3] → 1 removal.
Time Complexity
Time O(n log n). Sorting by end dominates; the greedy keep/remove pass is O(n).
Space Complexity
Space O(1) extra besides the input array, ignoring sorting implementation overhead.
Learning notes
- Why sort by end? — earliest finish leaves maximum room for later intervals.
- Why initialize
endvery small? — the first interval should always be eligible to keep. - Why
iv[0] >= end? — touching endpoints are non-overlapping for this problem. - Why update
end = iv[1]only when kept? — removed intervals should not constrain future choices. - Why count
removed++on overlap? — sorting by end means the current interval is no better than the one already kept. - Why this greedy is safe? — an exchange argument swaps any later-ending kept interval for the earlier-ending one.
"I first confirm touching endpoints like [1,2] and [2,3] are non-overlapping under the problem definition. I start with brute force by testing subsets of intervals, which is exponential time and O(n) space. I optimize by sorting by end time and greedily keeping compatible intervals, giving O(n log n) time and O(1) extra space."
Sorting by start, not end. Example: [[1,100],[2,3],[3,4]]. Sorting by start keeps [1,100] first and drops the two short intervals. Sort by end: pick [2,3], then [3,4] — remove [1,100].
Max non-overlapping set = Minimum Arrows to Burst Balloons (min points to stab all). Sort-by-end greedy is the shared core.
Same pattern, new tweaks
Sort by end time and greedily keep the earliest-finishing compatible interval:
| Variation | The one thing that changes | Time |
|---|---|---|
| Minimum Arrows to Burst Balloons | max non-overlapping set = minimum stabbing points | — |
| Maximum Length of Pair Chain | the same earliest-finish chain, counting length | — |
| Non-overlapping Intervals | removals = total − (max non-overlapping kept) | — |
| Course Schedule III | sort by deadline; greedily take courses, dropping the longest with a max-heap when you overrun | — |