Algorithms from zero
Classic greedy: jump game and gas station
You stand at the start of a row of stones, each labelled with how far you may leap from it. Can you reach the last stone? Your instinct says “try every path”—but that branches exponentially. The greedy trick is to stop thinking about paths and track a single number: the farthest stone you could possibly be standing on by now. Sweep left to right; if that frontier ever falls behind your current foot, you are stranded. One pass, no backtracking. The same change-one-number instinct cracks a second classic—driving a circular road of gas stations—where the whole question collapses to “is there enough fuel in total, and where do I start?” This lesson closes the greedy unit with two interview staples, both O(n).
After this lesson you can solve two famous greedy problems and explain the local quantity each one tracks. For Jump Game you can decide whether the last index is reachable by sweeping once and maintaining the farthest reachable index; you can state the failure test (“if the current index ever passes the frontier, you are stuck”) and argue why one number replaces searching every path. For Jump Game II you can count the minimum jumps with a greedy BFS-like level expansion: each “level” is the set of indices reachable with the current jump count, and you spend a jump exactly when you exhaust the current level. For Gas Station you can state the feasibility condition (a circular trip is possible iff total gas >= total cost) and find the start by resetting the candidate start every time the running tank goes negative—and you can argue why the reset is safe (no station you skipped could be a valid start either). You can show all three run in O(n) time and O(1) extra space. This is the last lesson of the greedy unit; next unit moves on from greedy to a new pattern.
Jump Game: track the farthest reachable index
You are given an array nums where nums[i] is the maximum jump length from index i. Starting at index 0, can you reach the last index? The brute-force answer explores every jump choice—exponential. The greedy insight: you never need to know which path got you somewhere, only how far you can possibly be. So carry one number, farthest = the largest index reachable so far.
Sweep i from left to right. Two things happen at each step:
- Reachability check. If
i > farthest, then no earlier index could launch you toi. There is a gap you cannot cross—returnfalse. (You are standing on a stone the frontier never reached.) - Extend the frontier. Otherwise
iis reachable, so fromiyou can jump up toi + nums[i]. Updatefarthest = max(farthest, i + nums[i]).
If the sweep finishes without ever failing the check, the last index was reachable—return true. (Equivalently: stop early the moment farthest >= n - 1.)
Here is the sweep on [2, 3, 1, 1, 4]. Watch farthest grow and notice it always stays at or ahead of i:
index i : 0 1 2 3 4
nums[i] : 2 3 1 1 4
| |
i+nums : 2 4 3 4 8
farthest: 2 4 4 4 8 <- frontier, monotonically non-decreasing
^^^^^^^^^^^^^^^^^^^^
i <= farthest at every step -> reachable, return trueThe frontier reaches index 4 (the last index) as early as i = 1. The single number farthest summarised every possible path—that is the whole greedy idea.
Why one number is enough. Reachability is “monotone”: if index j is reachable and j <= farthest, then so is everything between the old frontier and j + nums[j]. There are no holes behind the frontier to revisit. So the maximum reach is a complete summary of where you can be; nothing is lost by forgetting the individual paths.
Jump Game II: minimum jumps as level expansion
Same array, harder question: assuming the end is reachable, what is the fewest jumps to get there? Think of it as breadth-first search over indices. With 0 jumps you can only be at index 0. With 1 jump you can be anywhere in [1 .. nums[0]]. With 2 jumps, anywhere reachable from that whole first range. Each jump count defines a contiguous level: the band of indices reachable with exactly that many jumps.
You expand level by level. Keep three numbers:
jumps— jumps spent so far.curEnd— the right edge of the current level (the farthest you can be withjumpsjumps).farthest— the farthest you can reach by jumping from any index inside the current level.
Sweep i left to right (only up to n - 2; you do not jump from the goal). At each i, extend farthest. When i reaches curEnd, you have walked the entire current level, so you must spend one jump to move on: increment jumps and set curEnd = farthest (the next level’s right edge is everything the current level could reach). This is exactly BFS, but instead of a queue you ride the contiguous frontier—so it is O(n), not O(n) with queue overhead.
Gas Station: total fuel, then a self-correcting start
A circular route of n stations. Station i gives gas[i] fuel; driving from i to i+1 costs cost[i]. Start with an empty tank at some station, drive the full loop clockwise, return the starting index if the trip is possible, else -1. The tank must never go negative.
Two greedy facts solve it in one pass:
- Feasibility = total. Sum the net
gas[i] - cost[i]over all stations. Iftotal < 0, you burn more than you carry no matter where you start—return-1. Iftotal >= 0, a valid start is guaranteed to exist. The whole feasibility question reduces to one sum. - Find the start by resetting. Walk once, keeping a running
tank(net fuel since the candidate start) and astartindex. Add each station’s net totank. The instanttank < 0, the candidatestartcannot work—and crucially, neither can any station betweenstartandi. So jump the candidate toi + 1and resettank = 0. Keep going. Whentotal >= 0, whateverstartyou are left holding at the end is a correct answer.
The deep point is the safety of the reset, proved in the insets below: if you ran dry going from start to i, no station in that stretch is a viable start either, so you lose nothing by skipping all of them at once. That is what makes one pass sufficient.
Jump Game: can you reach the last index?
The state is one number, farthest. The loop does the reachability check, then extends the frontier.
1
function canJump(nums) {
2
let farthest = 0; // best index reachable so far
3
for (let i = 0; i < nums.length; i++) {
4
if (i > farthest) { // i is beyond the frontier
5
return false; // unreachable: stranded
6
}
7
farthest = Math.max(farthest, i + nums[i]); // extend the frontier from i
8
}
9
return true; // never got stranded
10
}
- L2 The whole state is one number: the farthest index reachable from anything seen so far. Starts at 0 (we begin standing on index 0).
- L4 Reachability check FIRST. If the current index has slipped past the frontier, no earlier index could launch us here -> a gap we cannot cross.
- L5 Return false the moment we are stranded. No path explored, no backtracking.
- L7 i is reachable, so from i we can jump to i + nums[i]. Keep the maximum: the frontier only ever moves forward.
- L9 Finished the sweep without ever failing the check -> the last index was reachable.
Jump Game II: minimum jumps via level expansion
Same farthest-reach idea, plus two more numbers to count BFS levels.
1
function jump(nums) {
2
let jumps = 0; // jumps spent so far
3
let curEnd = 0; // right edge of current level
4
let farthest = 0; // best reach from this level
5
for (let i = 0; i < nums.length - 1; i++) { // stop before the goal index
6
farthest = Math.max(farthest, i + nums[i]); // extend reach within level
7
if (i === curEnd) { // consumed the whole level
8
jumps++; // one jump buys the next level
9
curEnd = farthest; // its edge = everything reachable
10
}
11
}
12
return jumps;
13
}
- L5 Loop only to n-2: you never jump FROM the last index, you arrive at it. Looping to the end would over-count one jump.
- L6 While inside the current level, keep extending the farthest index any of its members can reach.
- L7 Reaching curEnd means we have walked the entire current level. To advance we must spend a jump.
- L8 Spend the jump.
- L9 The next level's right edge is the best reach we accumulated -> commit the frontier as the new level.
Running both on the same arrays
canJump returns a boolean; jump returns the minimum jump count (for inputs known to be reachable).
[3,2,1,0,4] fails because the 0 at index 3 is a trap: the best frontier reaches index 3 but never index 4. For [2,3,1,1,4] the minimum is 2 jumps (0 -> 1 -> 4): a greedy that always commits to the farthest reachable level is provably optimal.
Gas Station: feasibility plus a resetting start
One sweep tracks the global total (feasibility) and a local tank + start (the candidate). The reset is the whole trick.
1
function canCompleteCircuit(gas, cost) {
2
let total = 0; // net gas around the whole loop
3
let tank = 0; // running fuel since the candidate start
4
let start = 0; // current candidate starting station
5
for (let i = 0; i < gas.length; i++) {
6
const diff = gas[i] - cost[i]; // net fuel at station i
7
total += diff;
8
tank += diff;
9
if (tank < 0) { // ran dry before leaving i
10
start = i + 1; // none of start..i can begin the loop
11
tank = 0; // restart accounting from i+1
12
}
13
}
14
return total >= 0 ? start : -1; // feasible iff total net >= 0
15
}
- L2 Global accumulator: the net fuel over the entire circle. Its sign alone decides whether ANY solution exists.
- L3 Local accumulator: fuel collected since the current candidate start. This is what tells us if the candidate survives.
- L6 Net at this station: gas given minus cost to drive to the next station. Can be negative.
- L9 Tank went negative -> we cannot reach station i+1 from the current start.
- L10 Move the candidate past i. Key claim (proved in the insets): no station in start..i can be a valid start either, so skip them all.
- L11 Fresh tank: accounting begins again from the new candidate i+1.
- L14 If total net is non-negative a solution exists, and the surviving start is correct; otherwise no start works.
Circuit A has total net (1-3)+(2-4)+(3-5)+(4-1)+(5-2) = -2-2-2+3+3 = 0 >= 0, so a start exists; the reset logic lands on index 3. Circuit B has total net -1 < 0, so no start works and we return -1. Circuit C’s only viable start is index 4.
Let us step through the Jump Game sweep on [2, 3, 1, 1, 4] and watch the single number farthest summarise every path. Each frame shows the current index i, whether the reachability check passes (i <= farthest), and the updated frontier.
1
function canJump(nums) {
2
let farthest = 0;
3
for (let i = 0; i < nums.length; i++) {
4
if (i > farthest) return false;
5
farthest = Math.max(farthest, i + nums[i]);
6
}
7
return true;
8
}
Note the frontier farthest is monotonically non-decreasing: 0, 2, 4, 4, 4, 8. The check i > farthest never fired, so the last index is reachable. Contrast [3,2,1,0,4]: the frontier would stall at 3 (the 0 at index 3 adds nothing), and at i=4 the check 4 > 3 would fire return false.
Time: O(n) for all three
Every algorithm here is a single left-to-right sweep with O(1) work per index—a compare, an addition, a max. No nested loops, no backtracking, no path enumeration.
pass work per index total time extra space
Jump Game 1 O(1) O(n) O(1)
Jump Game II 1 O(1) O(n) O(1)
Gas Station 1 O(1) O(n) O(1)For Jump Game, the brute-force alternative (try every jump choice) is exponential; collapsing the path set into the single number farthest is what buys the linear time. For Jump Game II, the same level-expansion idea could be coded as a BFS with a queue—still O(n) work but with queue allocation and overhead; riding the contiguous frontier with three integers removes that constant-factor cost. For Gas Station, the naive approach tries each of the n stations as a start and simulates a full loop—O(n^2); the single-pass reset proves you only ever need one walk.
Space: O(1) for all three
Each algorithm keeps a fixed handful of integers regardless of input size: farthest for Jump Game; jumps, curEnd, farthest for Jump Game II; total, tank, start for Gas Station. No auxiliary array, no recursion stack. That is the signature of a clean greedy: a constant amount of running state that summarises everything you need to know.
The greedy lens. All three replace a search over many possibilities with a single local quantity that provably captures the optimum: the farthest reachable index, the current BFS level edge, the running tank since the last reset. Finding that one quantity—and proving it suffices—is the entire art of greedy design.
In Jump Game, what single quantity does the greedy sweep track, and what does it mean?
In Jump Game, when do you conclude the last index is NOT reachable?
In Jump Game II, why does the loop run only to index n-2 instead of n-1?
In Gas Station, what single condition decides whether ANY valid start exists?
In Gas Station, what happens the moment the running tank goes negative at station i?
Why is resetting the candidate start to i+1 (rather than start+1) safe in Gas Station?
Run the farthest-reach sweep on [1, 0, 2]. After processing index 0, farthest = 1. At index 1 (value 0), farthest stays 1. What is i at the step where the reachability check i > farthest first fails? (Enter that index.)
Why this works
Why total >= 0 guarantees a start in Gas Station. Suppose total >= 0. Run the algorithm; it ends holding some candidate start. Every reset happened because the tank went negative before reaching start, so the stretch from start to the end of the array never dipped below zero. What about wrapping from the end back around to start? The fuel used there equals total minus the (non-negative) fuel banked on the start..end stretch. Since total >= 0, that wrap-around portion cannot push the tank below zero either. So the full loop beginning at start always keeps the tank >= 0. The global sum being non-negative is therefore not just necessary but sufficient.
Common mistake
Mistake: returning -1 too eagerly, or checking the wrong condition. A common bug in Gas Station is returning -1 the first time the local tank goes negative. That is wrong: a negative tank only invalidates the current candidate, not the whole problem—you must keep sweeping, resetting the start, and decide feasibility from the global total at the end. The mirror mistake in Jump Game is testing nums[i] === 0 to detect failure. A 0 is harmless unless it sits exactly on the frontier with nothing reaching past it. The correct, sufficient failure test is purely positional: i > farthest.
Edge cases
Single-element and trap cases. Jump Game on [0]: the loop runs once at i=0, the check 0 > 0 is false (you are already on the last index), and it returns true—a length-1 array is trivially solved without jumping. Jump Game II on [0] returns 0 because the loop body (which runs to n-2 = -1) never executes: zero jumps needed. The classic trap is a 0 reachable but blocking: [3,2,1,0,4]. The frontier climbs to 3 but the 0 at index 3 extends nothing, so at i=4 the check 4 > 3 fires and it correctly returns false. Always test the array whose only zero sits exactly on the frontier.
More practice
The greedy recipe both problems share. (1) Identify the brute force (enumerate all paths / try every start) and its bad complexity. (2) Ask: is there a single local quantity that summarises everything I need, making the search unnecessary? Jump Game -> farthest reachable index. Gas Station -> running tank plus global total. (3) Define the update rule and the decision test on that quantity. (4) Prove the local choice never loses the optimum (monotone frontier; safe reset). (5) Confirm one O(1)-per-step pass suffices, giving O(n). When you can name the quantity and justify why it suffices, you have a greedy solution.
Explain the greedy insight behind Jump Game and Gas Station: what local quantity each tracks, the decision test, why the Gas Station reset is safe, the feasibility condition, and the complexity.
Two famous greedy problems, both solved by tracking a single local quantity in one O(n) pass.
Jump Game — farthest reachable index. Carry farthest, the largest index reachable so far. Sweep i left to right: if i > farthest you are stranded (return false); otherwise extend farthest = max(farthest, i + nums[i]). Finish the sweep and the last index is reachable. One number replaces searching every path because reachability is monotone—no holes behind the frontier.
Jump Game II — minimum jumps as level expansion. Treat jump counts as contiguous BFS levels. Keep jumps, curEnd (current level’s edge), farthest (best reach from this level). Loop to n-2 only; when i hits curEnd, spend a jump and set curEnd = farthest. Optimal and O(n) with three integers, no queue.
Gas Station — total fuel, then a self-correcting start.
- Feasibility: a circular trip is possible iff total net fuel
sum(gas[i] - cost[i]) >= 0. The whole question reduces to one sum. - Find the start: walk once with a running
tankand candidatestart. Whenevertank < 0, resetstart = i + 1andtank = 0. The survivingstartis correct whentotal >= 0. - Why the reset is safe: running dry from
starttoidisqualifies every station in that stretch as a start, so skipping them all loses nothing.
Complexity: all three are O(n) time and O(1) space—a fixed handful of integers, one pass, no recursion. The greedy art is finding the local quantity that provably captures the optimum (farthest reach, level edge, running tank) and proving the local choice never loses.
This closes the greedy unit: you have seen the exchange argument, interval scheduling, and now two staple greedy problems. The next unit moves on to a new algorithmic pattern.