Module P-15 — Greedy Algorithms: Local vs Global Optimum
What this module covers: Dynamic programming (Modules P-11 through P-14) considers every relevant subproblem before committing to an answer. A greedy algorithm does the opposite: make the locally best choice available right now, commit to it permanently, and never look back. This module covers when that shortcut is provably correct, and — just as importantly — a clear counterexample showing when it silently produces the wrong answer.
The Greedy Strategy
A greedy algorithm makes one pass, choosing at each step whatever looks best right now, with no reconsideration and no backtracking (contrast this directly with Module P-7's backtracking, which explicitly does undo choices that don't work out). This is fast — usually a single O(n) or O(n log n) pass — but it's only correct when the problem has a specific property: the locally best choice at each step never prevents reaching the globally best overall solution. Not every problem has that property, which is the entire reason this module exists alongside dynamic programming rather than replacing it.
Jump Game: Can You Reach the End?
Given an array where each value is the maximum jump length from that position, determine if you can reach the last index starting from index 0.
typescript
The greedy insight: you never need to remember which specific path got you to the farthest reachable point — only how far that point currently is. At each index, greedily extend farthestReachable as far as the current position allows, and check whether the current index has actually been reached yet. This works because "can I reach index i" only depends on the single number farthestReachable, not on any specific sequence of jumps that produced it — there's no scenario where remembering more detail about the path taken would ever change the answer.
Gas Station: Find the Valid Starting Point
Given gas available at each station around a circular route and the cost to travel from each station to the next, find a starting station from which a complete circuit is possible (guaranteed unique if a solution exists and the total gas covers the total cost).
typescript
The greedy leap here is subtler than Jump Game: the moment currentTank goes negative at station i, every station between the current start candidate and i can be ruled out in one step, without individually testing each one — because none of them could have accumulated more surplus gas by station i than starting exactly at start did, and even that wasn't enough. Resetting start = i + 1 and continuing the same single pass, rather than restarting the whole scan from scratch for each candidate, is what keeps this O(n) instead of the O(n²) a "try every possible starting station independently" approach would cost.
Interval Scheduling: Maximum Non-Overlapping Intervals
Given a set of intervals, select the maximum number that don't overlap with each other — directly building on Module F-10's interval vocabulary.
typescript
The greedy choice — always pick the interval that ends soonest among the remaining valid candidates — is provably optimal here: an interval that ends earlier can never be a worse choice than one ending later, because it leaves strictly more room for whatever comes after it, and it was compatible with everything selected so far by definition. Sorting by start time instead, and greedily picking the earliest-starting interval, does not work — a long interval that starts earliest could block out several shorter ones that would have fit if skipped, which is exactly the kind of counterexample worth testing by hand before trusting a greedy strategy.
When Greedy Fails: 0/1 Knapsack
This is worth stating plainly, because it's the most common way greedy reasoning goes wrong in practice: greedy-by-value-density does not solve 0/1 knapsack correctly, even though it feels intuitively reasonable.
typescript
Consider weights [10, 20, 30], values [60, 100, 120], capacity 50. Value density is highest for the first item (6/kg), then the second (5/kg), then the third (4/kg) — greedy takes items 1 and 2 (weight 30, value 160), then can't fit item 3 (weight 30 > remaining 20). But the actual optimal answer, found by Module P-13's knapsack01, is items 2 and 3 (weight 50, value 220) — strictly better, and greedy never finds it, because committing early to the first item permanently closes off that better combination. This is precisely why 0/1 knapsack needs Module P-13's full dynamic programming treatment (considering all combinations via the table) rather than a shortcut — the "take the best-looking option now" strategy doesn't have the greedy-choice property this problem needs. (The fractional knapsack variant — where items can be split, taking a partial amount — genuinely is solvable greedily by value density, precisely because splitting removes the all-or-nothing commitment that breaks greedy here.)
Where This Shows Up in Your Stack
Interval scheduling directly extends Module F-10: "maximum number of non-overlapping meetings that can be scheduled in one room" is precisely maxNonOverlapping, greedily picking whichever meeting ends soonest at each step.
Jump Game's reachability logic models feasibility checks in resource-constrained systems generally — "given these fixed transfer/retry limits at each step, can this process reach completion" is the same single-pass, farthest-reachable-point reasoning.
Gas Station's circular feasibility check models any scenario with cyclic resource replenishment and consumption — verifying a rotating on-call schedule or a cyclic buffer allocation scheme can sustain itself indefinitely without running out at some point in the cycle.
Recognizing when not to reach for greedy is arguably the more valuable production skill: 0/1 knapsack's failure mode above is a specific instance of a general trap — "the locally best-looking choice, chosen first, permanently forecloses a better combination available later" — worth checking for explicitly before shipping a greedy shortcut on any resource-allocation problem with discrete, all-or-nothing choices.
Summary
Greedy algorithms make one irreversible, locally-best choice per step, achieving speed (usually O(n) or O(n log n)) at the cost of only being correct on problems with the greedy-choice property.
Jump Game and Gas Station both work because the relevant state collapses to a single running number (farthest reachable point; running tank total) — no need to remember the specific path that produced it.
Interval scheduling's correct greedy choice is "pick whichever compatible interval ends soonest" — sorting by start time instead is a common, tempting mistake that breaks correctness.
0/1 knapsack is the canonical greedy failure case: value-density-first greedily commits early and can permanently foreclose a better combination — Module P-13's full dynamic programming approach is required precisely because this problem lacks the greedy-choice property.
The fractional variant of knapsack is greedy-solvable, because splitting items removes the all-or-nothing commitment that breaks the 0/1 version — a useful contrast for recognizing which variant of a problem you're actually facing.
This closes Practitioner. The Practitioner Capstone — DSA in Production: React's Virtual DOM, Diffing, and Tree Traversal — ties Module P-4's traversal patterns directly to how React actually reconciles UI updates, before Architect begins with heaps and priority queues.
Knowledge Check
Why does maxNonOverlapping sort intervals by their end time rather than their start time, and why does the module describe sorting by start time as "a common, tempting mistake"?
In canCompleteCircuit, why is it safe to skip individually testing every station strictly between the current start candidate and the station i where currentTank first goes negative?
Using the module's example (weights [10, 20, 30], values [60, 100, 120], capacity 50), why does the greedy value-density approach fail to find the actual optimal 0/1 knapsack solution?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functioncanJump(nums:number[]):boolean{let farthestReachable =0;for(let i =0; i < nums.length; i++){if(i > farthestReachable)returnfalse;// this position is unreachable — no jump could have gotten here farthestReachable = Math.max(farthestReachable, i + nums[i]);}returntrue;}canJump([2,3,1,1,4]);// truecanJump([3,2,1,0,4]);// false — stuck at index 3, which can only jump 0
functioncanCompleteCircuit(gas:number[], cost:number[]):number{let totalTank =0;// running total across the ENTIRE route — determines feasibility at alllet currentTank =0;// running total since the current candidate start — determines THIS start's validitylet start =0;for(let i =0; i < gas.length; i++){const net = gas[i]- cost[i]; totalTank += net; currentTank += net;if(currentTank <0){// Every station from `start` through `i` is invalid as a starting point:// if starting at `start` couldn't make it past `i`, starting anywhere strictly// between `start` and `i` (with less accumulated gas by that point) definitely can't either. start = i +1; currentTank =0;}}return totalTank >=0? start :-1;}
functionmaxNonOverlapping(intervals:[number,number][]):number{if(intervals.length ===0)return0;// Sort by END time — not start time — which is the specific greedy choice that makes this workconst sorted =[...intervals].sort((a, b)=> a[1]- b[1]);let count =1;let lastEnd = sorted[0][1];for(let i =1; i < sorted.length; i++){if(sorted[i][0]>= lastEnd){// this interval starts after the last selected one ends — no overlap count++; lastEnd = sorted[i][1];}}return count;}
// Tempting, but WRONG for 0/1 knapsack:// "always take the item with the best value-to-weight ratio that still fits"functionknapsackGreedyWrong(weights:number[], values:number[], capacity:number):number{const items = weights
.map((w, i)=>({ weight: w, value: values[i], ratio: values[i]/ w })).sort((a, b)=> b.ratio - a.ratio);// best value density firstlet totalValue =0;let remaining = capacity;for(const item of items){if(item.weight <= remaining){ totalValue += item.value; remaining -= item.weight;}}return totalValue;}