Patternwise

Greedy

Make the locally best choice and never look back.

Brute force
O(2ⁿ) recursion / O(n²) DP — try every path
With the pattern
O(n) — one pass (O(n log n) if sorting first)
Extra space
O(1)

In plain English

“Crossing a river on stepping stones, you keep track of the farthest stone you could possibly reach so far. Every stone you stand on might push that "farthest" mark further out. If you ever stand on a stone beyond the mark, you know you couldn't have gotten there.”

Why it's fast

Brute force explores every sequence of choices (exponential, or O(n²) DP for Jump Game). Greedy works when you can prove one simple summary — like farthest reachable index — captures everything that matters about the past. Then one pass updating that summary replaces the whole search tree.

Spot it when the problem says…

  • can you reach the end
  • minimum number of jumps / steps
  • maximize profit with unlimited transactions
  • assign / schedule to satisfy as many as possible
  • partition into as many parts as possible
  • circular route with gas / cost

Visualize

Jump game — track the farthest reach

nums[i] is the max jump from index i. Can you reach the last index from index 0?

0
2
1
3
2
1
3
1
4
4
5
0
6
1
7
2
01/07

Green bracket = every index we can certainly stand on. It starts as just index 0.

pythonline 2
1def can_jump(nums):2    reach = 0                        # farthest index reachable so far3    for i, step in enumerate(nums):4        if i > reach:5            return False             # stuck: can't even get to i6        reach = max(reach, i + step)7        if reach >= len(nums) - 1:8            return True9    return True

variables

reach
0

How to apply it

  1. 01Identify the single quantity to track (farthest reach, running surplus, last occurrence).
  2. 02Scan once, updating that quantity at each element.
  3. 03Detect failure early (current index beyond reach, surplus negative).
  4. 04Sanity-check the greedy choice with a small counterexample hunt — if one exists, you need DP.

Variations you'll meet

Farthest reach (Jump Game)

The visualizer's example.

python
def can_jump(nums: list[int]) -> bool:    reach = 0    for i, step in enumerate(nums):        if i > reach:              # stranded before i            return False        reach = max(reach, i + step)    return True

Min jumps as BFS levels (Jump Game II)

Treat each jump as a level: end is the edge of the current level, reach the edge of the next.

python
def jump(nums: list[int]) -> int:    jumps = end = reach = 0    for i in range(len(nums) - 1):        reach = max(reach, i + nums[i])        if i == end:               # must jump now            jumps += 1            end = reach    return jumps

Sort then greedy

Assign Cookies, intervals by end time: sorting exposes the obvious best choice.

Running surplus (Gas Station)

If the tank goes negative at i, no start between the old start and i works — restart at i + 1.

Common mistakes

  • Applying greedy without proof — Coin Change with arbitrary coins breaks greedy.
  • In Jump Game II, looping to the last index and counting an extra jump.
  • Checking i > reach after updating reach instead of before.
  • Sorting by the wrong key (start instead of end) in scheduling problems.

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Assign Cookies ↗Easy
  2. 02Best Time to Buy and Sell Stock II ↗Medium
  3. 03Jump Game ↗Medium
  4. 04Jump Game II ↗Medium
  5. 05Gas Station ↗Medium
  6. 06Partition Labels ↗Medium
  7. 07Hand of Straights ↗Medium
  8. 08Candy ↗Hard

Think you've got it?

Let the AI interviewer throw a Greedy problem at you and grade how you explain it.

Mock interview