/Projects
Coding patterns · 15 of 15

Greedy

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

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot greedy from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

Usually O(n) or O(n log n) with a sort Watch as reels
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?

jump-game-can.tsTypeScript
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
  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

gas-station.tsTypeScript
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

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.tsTypeScript
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.tsTypeScript
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
AI Engineer · Greedy