Greedy Classics
The gas station loop, the jump game, job sequencing with deadlines — the greedy problems worth memorizing.
The problem
A few greedy problems show up again and again — in interviews, in real systems, in your own code when you least expect them. The gas-station loop asks where to start a circular drive so you never run dry. The jump game asks whether you can leap to the end of an array. Job sequencing asks which deadline-bound tasks to run for maximum profit.
They look unrelated, but each hides the same trap: the naive answer is a nested loop that re-checks everything, and each has a one-pass greedy rule that collapses the work to linear. Learn the three and you will start spotting the pattern everywhere.
A first attempt
Take the gas station loop. You have gas[i] fuel at station i and it costs cost[i] to reach the next one. The brute-force answer tries every station as a starting point and simulates the full loop.
def can_complete_brute(gas, cost):
n = len(gas)
for start in range(n):
tank, ok = 0, True
for step in range(n):
i = (start + step) % n
tank += gas[i] - cost[i]
if tank < 0:
ok = False
break
if ok:
return start
return -1That is O(n^2): for each of n starts you simulate up to n steps. Fine for a quiz, hopeless for a large circular route. The same nested-loop shape haunts the other two classics.
The insight
Each problem has a single scalar you can carry in one pass that makes re-scanning unnecessary:
- Gas station: if total gas
≥total cost, a solution exists. Track a running tank; whenever it dips below zero, no station up to here can be the start, so jump the start to the next station and reset. One pass. - Jump game: track the farthest index reachable so far. If your current position ever exceeds that reach, you are stuck; otherwise you make it.
- Job sequencing: sort jobs by profit descending, and schedule each in the latest free slot on or before its deadline. High-profit jobs claim their time first.
In every case the greedy scalar summarizes the entire prefix, so you never look back.
How it works
Gas station — one running tank
Keep total (feasibility check) and tank (current run). Add gas[i] - cost[i] to both. When tank < 0, set the candidate start to i + 1 and reset tank to 0. If total >= 0 at the end, the candidate start works.
Jump game — farthest reach
Walk left to right holding reach, the farthest index you can get to. At index i, if i > reach you cannot proceed. Otherwise update reach = max(reach, i + nums[i]). You win if reach covers the last index.
Job sequencing — latest free slot
Sort jobs by profit descending. For each job, place it in the latest empty slot at or before its deadline (scan downward). Taking the latest slot leaves earlier slots open for tighter-deadline jobs.
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
diff = [-2,-2,-2, 3, 3]
tank dips below 0 at i=0,1,2 -> start jumps to 3
from i=3: 3, then +3=6, ... never negative
answer: start = 3 (total diff = 0 >= 0, feasible)The code
def can_complete_circuit(gas, cost):
total = tank = start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0: # nothing up to i can start the loop
start = i + 1
tank = 0
return start if total >= 0 else -1
def can_jump(nums):
reach = 0
for i, n in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + n)
return True
print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])) # 3
print(can_jump([2, 3, 1, 1, 4])) # True
print(can_jump([3, 2, 1, 0, 4])) # Falsefunction canCompleteCircuit(gas: number[], cost: number[]): number {
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;
}
function canJump(nums: number[]): boolean {
let reach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > reach) return false;
reach = Math.max(reach, i + nums[i]);
}
return true;
}
console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 3
console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // falseclass Classics {
static int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
static boolean canJump(int[] nums) {
int reach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > reach) return false;
reach = Math.max(reach, i + nums[i]);
}
return true;
}
public static void main(String[] args) {
System.out.println(canCompleteCircuit(
new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2})); // 3
System.out.println(canJump(new int[]{2, 3, 1, 1, 4})); // true
System.out.println(canJump(new int[]{3, 2, 1, 0, 4})); // false
}
}#include <stdio.h>
#include <stdbool.h>
int can_complete_circuit(int *gas, int *cost, int n) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < n; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
bool can_jump(int *nums, int n) {
int reach = 0;
for (int i = 0; i < n; i++) {
if (i > reach) return false;
int far = i + nums[i];
if (far > reach) reach = far;
}
return true;
}
int main(void) {
int gas[] = {1, 2, 3, 4, 5};
int cost[] = {3, 4, 5, 1, 2};
printf("%d\n", can_complete_circuit(gas, cost, 5)); /* 3 */
int a[] = {2, 3, 1, 1, 4};
int b[] = {3, 2, 1, 0, 4};
printf("%d\n", can_jump(a, 5)); /* 1 */
printf("%d\n", can_jump(b, 5)); /* 0 */
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
int canCompleteCircuit(std::vector<int> &gas, std::vector<int> &cost) {
int total = 0, tank = 0, start = 0;
for (size_t i = 0; i < gas.size(); i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
bool canJump(std::vector<int> &nums) {
int reach = 0;
for (size_t i = 0; i < nums.size(); i++) {
if ((int)i > reach) return false;
reach = std::max(reach, (int)i + nums[i]);
}
return true;
}
int main() {
std::vector<int> gas = {1, 2, 3, 4, 5}, cost = {3, 4, 5, 1, 2};
std::cout << canCompleteCircuit(gas, cost) << "\n"; // 3
std::vector<int> a = {2, 3, 1, 1, 4}, b = {3, 2, 1, 0, 4};
std::cout << canJump(a) << "\n"; // 1
std::cout << canJump(b) << "\n"; // 0
return 0;
}Complexity
| Problem | Brute force | Greedy time | Space |
|---|---|---|---|
| Gas station | O(n^2) | O(n) | O(1) |
| Jump game | O(n^2) | O(n) | O(1) |
| Job sequencing | O(n^2) | O(n log n) | O(n) |
Gas station and jump game are single linear passes; job sequencing is dominated by the profit sort plus a slot scan.
When to use it
Recognize the pattern, then prove it
These three are worth memorizing because the greedy rule is not obvious until you have seen it — "farthest reach" and "reset the start when the tank goes negative" are the kind of tricks you either know or reinvent painfully. But do not paste a greedy rule onto a lookalike problem without checking. Jump Game II (minimum jumps) needs a different greedy; the 0/1 knapsack looks greedy but is not — it needs dynamic programming. When the exchange argument does not hold, greedy quietly returns a wrong answer.
Practice
Recap
- Each classic replaces an O(n^2) nested simulation with a single greedy scalar carried in one pass.
- Gas station tracks a running tank, jump game tracks farthest reach, job sequencing fills the latest free slot by profit.
- Memorize the rules, but always confirm the exchange argument holds — lookalike problems (Jump Game II, 0/1 knapsack) need different tools.
How is this guide?
Last updated on