Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Make the choice that looks best now and never revisit it. It works only when you can argue an exchange: swapping any optimal solution's choice for yours never makes it worse.
A greedy algorithm makes the locally best choice and never revisits it. That is only correct when you can argue that some optimal answer starts with that choice (an exchange argument), so always explain why the greedy step is safe.
Typical cost: Usually O(n) or O(n log n) with a sort
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Gas Station
The problem statement, then the plan you would say out loud.
Circular route; find the start station that lets you finish, or -1.
Plan before you code
- If total gas < total cost, impossible.
- Otherwise, whenever the tank goes negative, the start must be after this station.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Jump game: can you reach the end?
1function canJump(nums: number[]): boolean {2 let reach = 0;3 for (let i = 0; i < nums.length; i++) {4 if (i > reach) return false; // stuck before i5 reach = Math.max(reach, i + nums[i]);6 }7 return true;8}1fun canJump(nums: IntArray): Boolean {2 var reach = 03 for (i in nums.indices) {4 if (i > reach) return false // stuck before i5 reach = maxOf(reach, i + nums[i])6 }7 return true8}1static boolean canJump(int[] nums) {2 int reach = 0;3 for (int i = 0; i < nums.length; i++) {4 if (i > reach) return false; // stuck before i5 reach = Math.max(reach, i + nums[i]);6 }7 return true;8}- Track the furthest index reachable so far.
- If we are past it, we can never get here.
- Greedily extend the reach.
3.2Solution
Strict TypeScript, type-checked and tested.
Gas Station
1function canCompleteCircuit(gas: number[], cost: number[]): number {2 const total = (xs: number[]) => xs.reduce((a, b) => a + b, 0);3 if (total(gas) < total(cost)) return -1;4 let start = 0, tank = 0;5 for (let i = 0; i < gas.length; i++) {6 tank += gas[i] - cost[i];7 if (tank < 0) {8 start = i + 1;9 tank = 0;10 }11 }12 return start;13}1fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {2 if (gas.sum() < cost.sum()) return -13 var start = 04 var tank = 05 for (i in gas.indices) {6 tank += gas[i] - cost[i]7 if (tank < 0) {8 start = i + 19 tank = 010 }11 }12 return start13}1static int canCompleteCircuit(int[] gas, int[] cost) {2 if (Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) return -1;3 int start = 0, tank = 0;4 for (int i = 0; i < gas.length; i++) {5 tank += gas[i] - cost[i];6 if (tank < 0) {7 start = i + 1;8 tank = 0;9 }10 }11 return start;12}Step by step
- Less gas than cost overall: impossible.
- Drive the loop, tracking the tank.
- Tank went negative: no start up to here works; restart after it.
- The last restart point is the answer.
Complexity: O(n) time, O(1) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
How do you know greedy is correct?
Why does Gas Station restart after the tank goes negative?
Greedy or DP for coin change?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Sort both; give the smallest cookie that fits.
Hint
Two passes: left-to-right, then right-to-left.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Jump Game II
Fewest jumps to reach the last index.
- Think in BFS layers: every index reachable with j jumps.
- Track the furthest reach of the current layer.
- When you hit the layer's end, jump.
1function jump(nums: number[]): number {2 let jumps = 0, end = 0, far = 0;3 for (let i = 0; i < nums.length - 1; i++) {4 far = Math.max(far, i + nums[i]);5 if (i === end) {6 jumps++;7 end = far;8 }9 }10 return jumps;11}Complexity: O(n) time, O(1) space
Partition Labels
Split a string into as many parts as possible so each letter appears in one part only.
- Record the last index of each letter.
- Extend the current part to the furthest last index seen.
- When i reaches that end, close the part.
1function partitionLabels(s: string): number[] {2 const last = new Map<string, number>();3 for (let i = 0; i < s.length; i++) last.set(s[i], i);4 const sizes: number[] = [];5 let start = 0, end = 0;6 for (let i = 0; i < s.length; i++) {7 end = Math.max(end, last.get(s[i])!);8 if (i === end) {9 sizes.push(end - start + 1);10 start = i + 1;11 }12 }13 return sizes;14}Complexity: O(n) time, O(1) space
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Using greedy without an exchange argument
- Sorting by the wrong key