When is greedy correct?Core idea
A greedy algorithm is correct when two things are true:
Greedy choice property
The locally best pick is part of some best overall answer.
Optimal substructure
After that pick, what is left is a smaller version of the same problem, still solvable the same way.
Interviews rarely want a full proof, but saying this kind of argument out loud is a strong signal.
Jump Game: can you reach the end?Pattern
Each number says how far you can jump from that spot. Track the furthest index you can reach so far. If you ever stand past that point, you are stuck.
function canJump(nums: number[]): boolean {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // this index can't be reached
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}Jump Game II: fewest jumpsPattern
Think of each jump as a window of positions you could land on. Scan the window, note the furthest you could go from anywhere in it, and when you reach the window's edge, that is one more jump.
function jump(nums: number[]): number {
let jumps = 0, currentEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currentEnd) { // edge of the current window
jumps++;
currentEnd = farthest;
}
}
return jumps;
}Gas StationPattern
If the total gas is less than the total cost, no start works. Otherwise, whenever your running tank drops below zero, no station up to here can be the start, so restart from the next one. The last restart point is the answer.
function canCompleteCircuit(gas: number[], cost: number[]): number {
let total = 0, tank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
total += gas[i] - cost[i];
tank += gas[i] - cost[i];
if (tank < 0) { tank = 0; start = i + 1; }
}
return total < 0 ? -1 : start;
}Non-overlapping intervalsPattern
Sort by end time and always keep the interval that finishes first, because it leaves the most room for the rest. This is the classic “activity selection” problem in disguise.
function eraseOverlapIntervals(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]);
let end = -Infinity, kept = 0;
for (const [s, e] of intervals) {
if (s >= end) { kept++; end = e; }
}
return intervals.length - kept;
}Candy: two passesPattern
Each child needs more candy than a neighbour with a lower rating. One pass left-to-right fixes the left neighbour rule, one pass right-to-left fixes the right one. No backtracking needed.
function candy(ratings: number[]): number {
const n = ratings.length;
const candies = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
}
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
return candies.reduce((a, b) => a + b, 0);
}When greedy fails, and when it worksCompare
| Problem | Greedy? | Why |
|---|---|---|
| Coin change (any coins) | ✗ Use DP | With coins [1, 3, 4] and amount 6, greedy takes 4+1+1 (3 coins) but 3+3 is 2. |
| 0/1 knapsack | ✗ Use DP | Taking the best value-per-weight item first can miss the best combination. |
| Interval scheduling, jump games, gas station | ✓ | They have the greedy choice property. |
| Minimum spanning tree | ✓ | Always adding the cheapest safe edge is provably optimal. |
| Huffman coding | ✓ | Merging the two least frequent symbols is provably optimal. |
Common mistakesPitfalls
Frequently asked questionsFAQ
How do I know a problem is greedy vs dynamic programming?
Test whether a locally optimal choice can be proven safe by an exchange argument. If the best current pick never blocks a better outcome, greedy. If you must weigh combinations of choices, dynamic programming. Coin change and knapsack are DP; jump games are greedy.
Do I need to prove greedy correctness in an interview?
Usually a short verbal justification is enough. State the greedy choice property, then sketch a one-line exchange argument: swap your pick into an optimal solution and show the result cannot get worse. Ten seconds of that signals real depth and normally satisfies the interviewer without a formal proof.
Which greedy problems appear most at FAANG?
Jump Game I and II, Gas Station, Non-overlapping Intervals, and Candy show up most often, followed by Task Scheduler and interval-scheduling variants. Amazon and Meta lean on jump and interval problems, while Google tends to probe the exchange-argument reasoning behind whatever greedy choice you make.
Now explain greedy algorithms to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.