Greedy Algorithms
Think of it like this
You're at a buffet with limited plate space. At each dish, you ask: "Is this worth the space?" If yes, take it; if not, skip it. You never go back to reconsider a dish you already passed.
That's greedy: make the locally best decision at each step, never reconsidering past choices. The trick is knowing when local-best guarantees global-best.
Greedy often fails: taking the most expensive item first doesn't guarantee the most valuable backpack (0/1 knapsack requires DP). But in carefully structured problems, it's provably optimal and far simpler than DP.
When Does Greedy Work?
A greedy algorithm is correct when the problem has the greedy choice property: a locally optimal choice is always part of some globally optimal solution.
This is proved using an exchange argument: assume an optimal solution doesn't make the greedy choice → show you can swap to the greedy choice without making it worse → contradiction → greedy is at least as good.
Pattern 1 — Activity Selection / Interval Scheduling
Select the maximum number of non-overlapping intervals.
Greedy strategy: always pick the interval that ends earliest. Why? An interval that ends earlier leaves more room for future intervals.
Intervals: [1,4], [2,3], [3,5], [4,6], [6,8]
Sort by end time: [2,3], [1,4], [3,5], [4,6], [6,8]
Pick [2,3] (ends at 3, no conflict)
Skip [1,4] (starts at 1 < 3, overlaps)
Pick [3,5] (starts at 3 ≥ 3, no conflict)
Skip [4,6] (starts at 4 < 5, overlaps)
Pick [6,8] (starts at 6 ≥ 5, no conflict)
Result: 3 intervals ✓ (optimal)function eraseOverlapIntervals(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[1] - b[1]); // sort by END time
let count = 0, end = -Infinity;
for (const [start, stop] of intervals) {
if (start >= end) {
end = stop; // take this interval
} else {
count++; // skip (remove) this interval
}
}
return count; // number of removals
}
// Meeting Rooms II — minimum rooms needed
function minMeetingRooms(intervals) {
const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
let rooms = 0, maxRooms = 0, e = 0;
for (let s = 0; s < starts.length; s++) {
if (starts[s] < ends[e]) rooms++; // new meeting starts before any ends → need room
else { rooms--; e++; } // a meeting ended, reuse that room
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}Pattern 2 — Jump Game
Can you reach the last index? What is the minimum number of jumps?
Greedy: at each position, track the farthest you can reach. If you can't reach the current position, you're stuck.
nums = [2, 3, 1, 1, 4] (value = max jump from that index)
Position 0: can reach up to 0+2=2
Position 1: can reach up to 1+3=4 (beyond end) → YES ✓// Can reach end? — O(n) greedy
function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // stuck — can't reach position i
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}
// Minimum jumps to reach end — O(n) greedy
function jumpMinimum(nums) {
let jumps = 0, currentEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]); // track max reachable
if (i === currentEnd) { // at boundary of current jump range
jumps++;
currentEnd = farthest; // extend boundary with a jump
}
}
return jumps;
}
// nums=[2,3,1,1,4]
// i=0: farthest=2, at currentEnd(0) → jump! jumps=1, end=2
// i=1: farthest=4
// i=2: farthest=4, at currentEnd(2) → jump! jumps=2, end=4 ← done
// Answer: 2 jumps ✓Pattern 3 — Task Scheduling with Cooldown
Schedule n tasks with a cooldown period k between same task types. Minimum time needed?
Greedy: always schedule the most frequent remaining task first.
function leastInterval(tasks, n) {
const freq = Array(26).fill(0);
for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
freq.sort((a, b) => b - a);
const maxFreq = freq[0];
// How many tasks have the max frequency?
const maxCount = freq.filter(f => f === maxFreq).length;
// Formula: max of (actual task count) and (ideal schedule with idle slots)
const ideal = (maxFreq - 1) * (n + 1) + maxCount;
return Math.max(tasks.length, ideal);
}Pattern 4 — Fractional Knapsack
Unlike 0/1 knapsack (which needs DP), fractional knapsack (you can take part of an item) is greedy:
function fractionalKnapsack(capacity, items) {
// Greedy: sort by value/weight ratio, take highest ratio first
items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let totalValue = 0;
for (const { weight, value } of items) {
if (capacity >= weight) {
totalValue += value; // take whole item
capacity -= weight;
} else {
totalValue += value * (capacity / weight); // take fraction
break;
}
}
return totalValue;
}Pattern 5 — Greedy on Strings
Remove k digits to make the smallest number:
// Remove k digits from number string to get smallest result
function removeKdigits(num, k) {
const stack = [];
for (const digit of num) {
// Remove larger preceding digits (greedy: smaller digits at front)
while (k > 0 && stack.length && stack[stack.length - 1] > digit) {
stack.pop();
k--;
}
stack.push(digit);
}
// If k remains, remove from the end (already sorted, so remove largest = last)
while (k-- > 0) stack.pop();
// Remove leading zeros
const result = stack.join('').replace(/^0+/, '') || '0';
return result;
}Greedy (Activity Selection)
Given intervals (start, end). Goal: Pick max non-overlapping activities.
Greedy vs DP — How to Decide
| Question | Greedy | DP |
|---|---|---|
| Can past choices affect future validity? | No | Yes |
| Does local best guarantee global best? | Yes (provable) | No |
| Need to enumerate all possibilities? | No | Sometimes |
| Solution space | Single path | Multiple paths |
| Time complexity | Usually O(n log n) | Usually O(n²) or O(n·k) |
Example of greedy failing (use DP instead):
Coin change with denominations [1, 3, 4], target = 6
Greedy (pick largest first): 4 + 1 + 1 = 3 coins
DP (optimal): 3 + 3 = 2 coins ✓
Greedy fails here because 4 isn't always the best first choice.
(It works for specific coin systems like US coins [1, 5, 10, 25] but not arbitrary ones)Real-World Frontend Application
- GZIP/Huffman encoding: Compresses JavaScript bundles by greedily merging the two lowest-frequency character nodes into a combined node — always the local-best merge leads to the globally optimal prefix tree
- TCP congestion control: Always probe for more bandwidth using a greedy strategy (slow-start, additive increase)
- CSS
autolayout: The browser's greedy shrink/grow algorithm for flex children approximates optimal space distribution in one pass - React Scheduler work-loop: Greedily picks the highest-priority task that can complete within the current frame budget
Common Mistakes
| Mistake | Example | Fix |
|---|---|---|
| Applying greedy to 0/1 knapsack | Gets wrong answer | Use DP — you can't "undo" taking an item |
| Wrong sort direction | Sorting by start instead of end for intervals | Sort by END time for "maximum non-overlapping" |
| Not proving correctness | Submitting greedy that passes easy cases but fails edge cases | Think about exchange argument or try to break it |
| Forgetting to sort first | Greedy on unsorted data usually fails | Almost all greedy algorithms require sorted input |
Key Problems to Solve
| # | Problem | Strategy | Difficulty |
|---|---|---|---|
| 1 | Assign Cookies | Sort both, match smallest cookie to smallest appetite | Easy |
| 2 | Jump Game | Track max reachable index | Medium |
| 3 | Jump Game II | Count jumps at range boundaries | Medium |
| 4 | Non-Overlapping Intervals | Sort by end, skip overlapping | Medium |
| 5 | Meeting Rooms II | Sort starts/ends separately | Medium |
| 6 | Task Scheduler | Max frequency formula | Medium |
| 7 | Gas Station | Circular greedy — total gain ≥ 0 is possible | Medium |
| 8 | Remove K Digits | Monotonic stack greedy | Medium |
| 9 | Candy Distribution | Two-pass greedy (left then right) | Hard |
| 10 | IPO (Maximize Capital) | Greedy with priority queues | Hard |