Greedy pattern

Take the locally best choice, and prove it is safe.

Part 1 of 5

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.

Why it works

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.

Scheduling by earliest endReach / jump problemsAssign or pair to minimise costA sort followed by one pass
Part 2 of 5

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.

Problem

Circular route; find the start station that lets you finish, or -1.

Plan before you code

  1. If total gas < total cost, impossible.
  2. Otherwise, whenever the tank goes negative, the start must be after this station.
Part 3 of 5

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?

TypeScriptKotlinJava
jump-game-can.tsTypeScriptCopy
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}
8 linesUTF-8TypeScript
jump-game-can.ktKotlinCopy
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}
8 linesUTF-8Kotlin
jump-game-can.javaJavaCopy
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}
8 linesUTF-8Java
  1. Track the furthest index reachable so far.
  2. If we are past it, we can never get here.
  3. Greedily extend the reach.

3.2Solution

Strict TypeScript, type-checked and tested.

Gas Station

TypeScriptKotlinJava
gas-station.tsTypeScriptCopy
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}
13 linesUTF-8TypeScript
gas-station.ktKotlinCopy
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}
13 linesUTF-8Kotlin
gas-station.javaJavaCopy
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}
12 linesUTF-8Java

Step by step

  1. Less gas than cost overall: impossible.
  2. Drive the loop, tracking the tank.
  3. Tank went negative: no start up to here works; restart after it.
  4. The last restart point is the answer.

Complexity: O(n) time, O(1) space

Part 4 of 5

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?
Show that you can swap the greedy choice into any optimal solution without making it worse. If you cannot argue that, consider dynamic programming.
Why does Gas Station restart after the tank goes negative?
Any start between the old start and this point would arrive here with even less fuel, so none of them can work.
Greedy or DP for coin change?
Greedy works for coin systems like 1, 5, 10, 25 but fails for [1, 3, 4] with amount 6. Dynamic programming is always correct.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyAssign Cookies
Hint

Sort both; give the smallest cookie that fits.

HardCandy
Hint

Two passes: left-to-right, then right-to-left.

Part 5 of 5

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
Medium

Jump Game II

Fewest jumps to reach the last index.

  1. Think in BFS layers: every index reachable with j jumps.
  2. Track the furthest reach of the current layer.
  3. When you hit the layer's end, jump.
jump-game-ii.tsTypeScriptCopy
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}
11 linesUTF-8TypeScript

Complexity: O(n) time, O(1) space

Medium

Partition Labels

Split a string into as many parts as possible so each letter appears in one part only.

  1. Record the last index of each letter.
  2. Extend the current part to the furthest last index seen.
  3. When i reaches that end, close the part.
partition-labels.tsTypeScriptCopy
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}
14 linesUTF-8TypeScript

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