Greedy Algorithms
Take the best-looking option right now and never reconsider. Sometimes optimal, sometimes badly wrong, and the interview skill is knowing which before you commit.
By the end: Spot when greedy is provably correct and when it is a trap.
A greedy algorithm makes the choice that looks best right now and never revisits it.
When that works, the code is astonishingly short — often a single loop where dynamic programming would need a table. When it does not work, it produces a confidently wrong answer, and the failure is silent. So this lesson is half technique and half judgement: how to write greedy solutions, and how to tell in the interview whether you are allowed to.
A greedy algorithm that is correct
Start with a problem where greedy provably works, so you can see the shape before you learn to distrust it. You are given stock prices day by day and may buy and sell as often as you like. Maximise profit.
function maxProfit(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
// Every day the price rose, pocket the difference. No lookahead at all.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
}
return profit;
}
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 7 = (5-1) + (6-3)
console.log(maxProfit([1, 2, 3, 4, 5])); // 4 one long climb
console.log(maxProfit([7, 6, 4, 3, 1])); // 0 never buy
console.log(maxProfit([2])); // 0 nothing to doOutput
Why is that right? Any profitable sequence of trades — buy low on day i, sell high on day j — has the same total as taking every daily rise in between, because the intermediate terms cancel: (p₂-p₁) + (p₃-p₂) = p₃-p₁. And every daily fall is skipped, so nothing negative is ever added. The greedy total is therefore an upper bound that is also achievable, which is exactly what a correctness argument looks like.
Where greedy breaks: coin change
Now the counterexample every candidate should have ready. Make a target amount with the fewest coins, using an arbitrary coin set.
// Greedy: always take the largest coin that still fits.
function coinsGreedy(coins, amount) {
const sorted = [...coins].sort((a, b) => b - a);
const used = [];
let left = amount;
for (const coin of sorted) {
while (left >= coin) { used.push(coin); left -= coin; }
}
return left === 0 ? used : null;
}
// Correct: dynamic programming over every amount up to the target.
function coinsDP(coins, amount) {
const best = new Array(amount + 1).fill(Infinity);
best[0] = 0;
for (let a = 1; a <= amount; a++)
for (const coin of coins)
if (coin <= a) best[a] = Math.min(best[a], best[a - coin] + 1);
return best[amount] === Infinity ? null : best[amount];
}
// On a "canonical" coin system, greedy happens to be right.
console.log('coins [25,10,5,1] for 30:', coinsGreedy([25, 10, 5, 1], 30), '| optimal count', coinsDP([25, 10, 5, 1], 30));
// On this one it is not.
const odd = [1, 3, 4];
const greedy = coinsGreedy(odd, 6);
console.log('coins [1,3,4] for 6: greedy', greedy, '=', greedy.length, 'coins');
console.log('coins [1,3,4] for 6: optimal is', coinsDP(odd, 6), 'coins → [3,3]');
console.log('Greedy took the 4, then needed two 1s. It cannot undo the 4.');Output
The test to run in your head
Before committing to greedy, ask three questions.
- Does a locally best choice ever block a better future? If you can imagine a case where taking the big coin, the long interval, or the nearest item paints you into a corner, greedy is suspect.
- Can I state why the greedy choice is safe? If no exchange or bound argument comes to mind in thirty seconds, treat that as evidence against greedy rather than a gap in your recall.
- Can I find a small counterexample? Try three or four elements by hand. Greedy failures usually show up at tiny sizes, which is why brute-force checking is so effective.
// A tiny harness: try greedy on all small coin sets and amounts, compare to DP.
function coinsGreedyCount(coins, amount) {
const sorted = [...coins].sort((a, b) => b - a);
let left = amount, count = 0;
for (const coin of sorted) while (left >= coin) { left -= coin; count++; }
return left === 0 ? count : Infinity;
}
function coinsDPCount(coins, amount) {
const best = new Array(amount + 1).fill(Infinity);
best[0] = 0;
for (let a = 1; a <= amount; a++)
for (const c of coins) if (c <= a) best[a] = Math.min(best[a], best[a - c] + 1);
return best[amount];
}
const failures = [];
// Coin sets always include 1 so every amount is reachable.
for (let b = 2; b <= 7; b++)
for (let c = b + 1; c <= 9; c++)
for (let amount = 1; amount <= 20; amount++) {
const set = [1, b, c];
if (coinsGreedyCount(set, amount) !== coinsDPCount(set, amount)) {
failures.push({ set: set.join(','), amount, greedy: coinsGreedyCount(set, amount), optimal: coinsDPCount(set, amount) });
}
}
console.log('coin sets tested: 1..9 triples, amounts 1..20');
console.log('cases where greedy is wrong:', failures.length);
console.log('first five:');
failures.slice(0, 5).forEach(f => console.log(` [${f.set}] amount ${f.amount}: greedy ${f.greedy}, optimal ${f.optimal}`));Output
The greedy patterns that keep appearing
Sort by one key, then sweep
// Choose the maximum number of non-overlapping activities.
function maxActivities(activities) {
// Sort by END time. This is the whole insight.
const sorted = [...activities].sort((a, b) => a[1] - b[1]);
const chosen = [];
let lastEnd = -Infinity;
for (const [start, end] of sorted) {
if (start >= lastEnd) { chosen.push([start, end]); lastEnd = end; }
}
return chosen;
}
const acts = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11]];
console.log('chosen:', maxActivities(acts));
console.log('count: ', maxActivities(acts).length);
// Sorting by START time instead gives a worse answer.
function byStart(activities) {
const sorted = [...activities].sort((a, b) => a[0] - b[0]);
const chosen = []; let lastEnd = -Infinity;
for (const [s, e] of sorted) if (s >= lastEnd) { chosen.push([s, e]); lastEnd = e; }
return chosen;
}
console.log('sorted by start:', byStart(acts), '→', byStart(acts).length, 'activities');Output
Track a running best, or a reachable frontier
function canJump(nums) {
let furthest = 0; // the furthest index reachable so far
for (let i = 0; i < nums.length; i++) {
if (i > furthest) return false; // this index is unreachable, so is the end
furthest = Math.max(furthest, i + nums[i]);
}
return true;
}
// The minimum number of jumps, same idea with a level boundary.
function minJumps(nums) {
let jumps = 0, currentEnd = 0, furthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
furthest = Math.max(furthest, i + nums[i]);
if (i === currentEnd) { jumps++; currentEnd = furthest; } // must jump now
}
return jumps;
}
console.log('[2,3,1,1,4] reachable:', canJump([2, 3, 1, 1, 4]), '| jumps:', minJumps([2, 3, 1, 1, 4]));
console.log('[3,2,1,0,4] reachable:', canJump([3, 2, 1, 0, 4]));
console.log('[0] reachable:', canJump([0]), '| jumps:', minJumps([0]));
console.log('[2,1] jumps:', minJumps([2, 1]));Output
Two-pass: fix left-to-right, then right-to-left
// Every child gets at least one candy, and more than any adjacent child
// with a lower rating. Minimise the total.
function candy(ratings) {
const n = ratings.length;
const give = new Array(n).fill(1);
// Left to right: satisfy the "greater than my left neighbour" rule.
for (let i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1]) give[i] = give[i - 1] + 1;
// Right to left: satisfy the other rule without breaking the first.
for (let i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1]) give[i] = Math.max(give[i], give[i + 1] + 1);
return { total: give.reduce((a, b) => a + b, 0), give };
}
console.log(candy([1, 0, 2])); // total 5, [2,1,2]
console.log(candy([1, 2, 2])); // total 4, [1,2,1]
console.log(candy([1, 3, 2, 2, 1])); // total 7
console.log(candy([5])); // total 1Output
Greedy plus a heap
// A heap is often the data structure that makes a greedy rule efficient.
class MinHeap {
constructor() { this.a = []; }
get size() { return this.a.length; }
peek() { return this.a[0]; }
push(v) {
this.a.push(v);
let i = this.a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p] <= this.a[i]) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
pop() {
const top = this.a[0], last = this.a.pop();
if (this.a.length) {
this.a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let small = i;
if (l < this.a.length && this.a[l] < this.a[small]) small = l;
if (r < this.a.length && this.a[r] < this.a[small]) small = r;
if (small === i) break;
[this.a[small], this.a[i]] = [this.a[i], this.a[small]];
i = small;
}
}
return top;
}
}
function minMeetingRooms(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const endTimes = new MinHeap(); // end times of rooms in use
for (const [start, end] of sorted) {
// Greedy: reuse a room if its meeting has already finished.
if (endTimes.size && endTimes.peek() <= start) endTimes.pop();
endTimes.push(end);
}
return endTimes.size; // peak concurrency
}
console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]])); // 2
console.log(minMeetingRooms([[7, 10], [2, 4]])); // 1
console.log(minMeetingRooms([[1, 5], [2, 6], [3, 7]])); // 3
console.log(minMeetingRooms([[1, 2]])); // 1Output
Greedy on strings and characters
function partitionLabels(s) {
// Where does each character last occur?
const lastIndex = new Map();
for (let i = 0; i < s.length; i++) lastIndex.set(s[i], i);
const sizes = [];
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
// The current piece must extend at least to this character's last position.
end = Math.max(end, lastIndex.get(s[i]));
if (i === end) { sizes.push(end - start + 1); start = i + 1; }
}
return sizes;
}
console.log(partitionLabels('ababcbacadefegdehijhklij')); // [9,7,8]
console.log(partitionLabels('eccbbbbdec')); // [10]
console.log(partitionLabels('a')); // [1]Output
function canCompleteCircuit(gas, cost) {
let total = 0, tank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
const gain = gas[i] - cost[i];
total += gain;
tank += gain;
// If the tank goes negative, no start before or at i can work.
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}
console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 3
console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3])); // -1
console.log(canCompleteCircuit([5], [4])); // 0Output
Greedy versus dynamic programming
// Maximum subarray sum. Kadane's algorithm is greedy: at each element, either
// extend the running subarray or start fresh — whichever is larger.
function maxSubarrayGreedy(nums) {
let best = nums[0], running = nums[0];
for (let i = 1; i < nums.length; i++) {
running = Math.max(nums[i], running + nums[i]); // the greedy choice
best = Math.max(best, running);
}
return best;
}
// The DP framing: best[i] = the best sum ending exactly at i.
function maxSubarrayDP(nums) {
const best = new Array(nums.length);
best[0] = nums[0];
for (let i = 1; i < nums.length; i++) best[i] = Math.max(nums[i], best[i - 1] + nums[i]);
return Math.max(...best);
}
const data = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log('greedy:', maxSubarrayGreedy(data), '| dp:', maxSubarrayDP(data));
console.log('all negative:', maxSubarrayGreedy([-3, -1, -2]), maxSubarrayDP([-3, -1, -2]));
console.log('single:', maxSubarrayGreedy([7]), maxSubarrayDP([7]));
console.log('Same algorithm. Greedy is the DP with the table collapsed to one variable.');Output
Complexity
- Sort-then-sweep —
O(n log n)time, dominated by the sort;O(1)orO(n)space depending on whether you copy the input. - Single-pass with a running best —
O(n)time,O(1)space. Jump game, Kadane, gas station. - Greedy plus a heap —
O(n log n)time,O(n)space. - Two-pass —
O(n)time,O(n)space for the intermediate array.
Notice what is absent: no exponential cases, and no O(n × target) tables. When greedy is valid it is nearly always the fastest solution available, which is why it is worth the risk of checking.
Your turn: five greedy problems
findContentChildren(children, cookies)— each child has a greed factor, each cookie a size. Sort both, then match the smallest adequate cookie to the least greedy child. Return how many children you can satisfy.eraseOverlapIntervals(intervals)— the fewest intervals to remove so none overlap. Same insight as activity selection: keep the earliest-finishing ones.largestNumber(nums)— arrange the numbers to form the largest possible value. The comparator is the trick: sort by(b + a).localeCompare(a + b)on the string forms.numRescueBoats(people, limit)— each boat carries at most two people within a weight limit. Sort, then two pointers pairing the lightest with the heaviest.reorganizeString(s)— rearrange so no two adjacent characters match. Repeatedly place the most frequent remaining character that is not the one you just placed; return''if impossible.
Output
Recap
- Greedy takes the locally best option and never reconsiders. When it is valid it beats every alternative; when it is not, it fails silently.
- Justify it with an exchange argument ("swapping in the greedy choice never makes an optimal solution worse") or a bound ("this total cannot be exceeded").
- Coins
[1,3,4]for6is the counterexample to keep in your pocket: greedy says three coins, the answer is two. - The recurring shapes are sort-then-sweep (activity selection, intervals), a running frontier (jump game, Kadane, gas station), two opposing passes (candy), and sort-plus-heap (meeting rooms).
- Greedy is dynamic programming whose table collapsed to a single variable — so if a decision needs to look back at combinations of earlier choices, reach for the table instead.