Algorithms from zero
Greedy: code reading
Crux Read real greedy snippets: an interval scheduler with the wrong sort key, a greedy that loses to DP, and a Gas Station scan. Predict the behaviour and pick the highest-leverage fix.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at senior altitude — in orbitGreedy bugs are quiet: the code runs, returns something plausible, and is wrong only on the inputs you did not test. Read each snippet the way you would in review — find the choice that is not provably safe, then pick the fix a senior engineer makes first.
Goal
Practise the loop you run on every greedy: read the local choice, decide whether it is provably optimal, and reach for the right sort key, the right invariant, or DP — before trusting the output.
Snippet 1 — the interval scheduler
// Goal: pick the MAXIMUM number of non-overlapping intervals.
function maxNonOverlapping(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]); // sort by START
let count = 0, lastEnd = -Infinity;
for (const [start, end] of sorted) {
if (start >= lastEnd) { count++; lastEnd = end; }
}
return count;
}
// maxNonOverlapping([[1, 10], [2, 3], [4, 5]]) -> ? Quiz
Completed
What does this return on [[1,10], [2,3], [4,5]], and what is the one-line fix?
Heads-up Sort-by-start takes the long [1,10] first and is then blocked from both short intervals, returning 1, not 2. Sort-by-start is the key for MERGING intervals, not maximization.
Heads-up [1,10] overlaps both [2,3] and [4,5], so they can never all be chosen. With the start-sort it picks only [1,10], returning 1.
Heads-up Removing the sort makes it wrong, not faster — the greedy depends on order. The defect is the KEY (start vs finish), and the algorithm is already O(n log n).
Snippet 2 — a greedy that loses to DP
// "Fewest coins for `amount`" by always taking the largest coin that fits.
function greedyCoins(coins, amount) {
const sorted = [...coins].sort((a, b) => b - a);
let left = amount, count = 0;
for (const c of sorted) {
while (left >= c) { left -= c; count++; }
}
return left === 0 ? count : Infinity;
}
// greedyCoins([1, 5, 6, 9], 11) -> ? (DP optimum is 2: 5 + 6) Quiz
Completed
greedyCoins([1,5,6,9], 11) returns 3 (9+1+1) but the DP optimum is 2 (5+6). Which statement correctly diagnoses this?
Heads-up Ascending order would only make greedy take many 1s — even worse. The failure is intrinsic to the denomination set, not the sort direction. DP is the fix.
Heads-up 5 + 6 = 11 uses exactly 2 coins, beating greedy's 3. DP minimizes exhaustively and is correct; greedy returns the worse answer.
Heads-up The guard only reports infeasibility; it has nothing to do with optimality. Even with a clean guard, greedy still returns 3 for this denomination set. Only DP guarantees the minimum.
Snippet 3 — the Gas Station scan
function canCompleteCircuit(gas, cost) {
let total = 0, tank = 0, start = 0;
for (let i = 0; i < gas.length; i++) {
const diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
} Quiz
Completed
A reviewer wants to delete the `total` variable and return `start` directly, arguing the reset already finds the answer. Why must `total` stay?
Heads-up Drop `total` and the function can return a bogus start on infeasible inputs (e.g. total net fuel negative), where it must return -1. `total` is the load-bearing feasibility check, not debug output.
Heads-up The tank is reset by the `tank = 0` line inside the if, independent of `total`. `total` plays no role in resets — its only job is the final feasibility verdict.
Heads-up They are different: `tank` is net fuel since the current candidate start (decides resets), `total` is net fuel over the whole loop (decides feasibility). Collapsing them breaks both roles.
Snippet 4 — Jump Game II loop bound
function jump(nums) {
let jumps = 0, curEnd = 0, farthest = 0;
for (let i = 0; i < nums.length; i++) { // loops to n-1
farthest = Math.max(farthest, i + nums[i]);
if (i === curEnd) { jumps++; curEnd = farthest; }
}
return jumps;
}
// jump([2, 3, 1, 1, 4]) -> ? (true minimum is 2) Quiz
Completed
This returns 3 on [2,3,1,1,4] but the minimum is 2. What is the off-by-one bug, and the fix?
Heads-up Starting at 1 would over-count from the first jump and break the [0]-length-1 case (which needs 0 jumps). The real bug is the loop bound — it must stop at n-2.
Heads-up The frontier (farthest reachable) only ever grows — Math.max is correct. Using min would collapse it and report unreachable. The defect is the loop bound.
Heads-up 0 -> 1 -> 4 reaches the end in 2 jumps. Looping to n-1 spends a spurious third jump on the goal index itself; stopping at n-2 fixes it.
Recap
Every greedy is read the same way: name the local choice, then ask whether it is provably safe. Snippet 1 used the wrong sort key (start instead of finish) for maximization; snippet 2 used greedy on a denomination set without the greedy-choice property, where only DP is correct; snippet 3 showed the global feasibility invariant (total >= 0) is load-bearing, separate from the local reset; snippet 4 was the classic Jump Game II off-by-one (loop to n-2, never jump from the goal). Diagnose the unsafe choice, then fix the key, the invariant, or fall back to DP.