TechPrep
Search spaces and optimisationReadLabPracticeCheck

Greedy, and how to defend it

Make the locally best choice when you can prove an exchange argument shows it never hurts.

Jump Game II. nums[i] is the maximum jump length from index i. Starting at index 0, return the minimum number of jumps to reach the last index (it is always reachable).

Signals that point here

The idea

This is BFS in disguise: all indices reachable in j jumps form a contiguous range, so you only need the range's end and the farthest point reachable from inside it. When i hits the end of the current layer, take a jump and the next layer's end becomes far.

A greedy answer needs a defence. The standard one is an exchange argument: take any optimal solution, swap its first choice for the greedy choice, and show it is no worse. If you cannot sketch that in two sentences, propose DP instead and say why.

def min_jumps(nums: list[int]) -> int:
    jumps = layer_end = farthest = 0
    for i in range(len(nums) - 1):        # never jump FROM the last index
        farthest = max(farthest, i + nums[i])
        if i == layer_end:                # finished this layer: take a jump
            jumps += 1
            layer_end = farthest
    return jumps

Complexity

O(n) time, O(1) space.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: min_jumps([2, 3, 1, 1, 2, 1, 4])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return the minimum number of intervals to remove so the rest do not overlap.
  2. Find the starting gas station that lets you complete the circuit, or -1.
  3. Partition a string into as many parts as possible so each letter appears in at most one part.

Check yourself

What argument usually proves a greedy algorithm correct?

An exchange argument: replacing an optimal solution's choice with the greedy one does not make it worse.

Why loop only to len(nums) - 1?

You never need to jump from the last index; including it can add one jump too many.

Saved in this browser.