Clinic #27: Jump Game

Pattern: Greedy · LC 55

Shows a catalog of five moves for attacking a problem. This clinic is the move called greedy (grab the best-looking choice now, never look back), used on a problem where that can be proven safe.

Before you start. Algorithm Design Patterns showed that “grab the best-looking choice and never look back” can be flatly wrong: with coins of 1, 3 and 4, grabbing the 4 first for an amount of 6 costs you a coin. Here you meet the same plan on a problem where it can never be wrong, and the whole skill is seeing why. The only other thing you need is a list: numbers in a row, each in a numbered slot starting from 0.

The idea in 30 seconds

Jump Game asks only yes or no: can you reach the last stone, when each stone’s number is your longest allowed stride? So you never have to choose a path.
Because any shorter stride is allowed, the reachable stones run unbroken from the start, with no gaps.
So one number, the reach, holds the whole answer. That unbroken run is the loop’s invariant, a fact true at every step.
Walk left to right, push the reach at each stone. Arrive at a stone past the reach and you are stranded: the answer is no.
This is greedy, taking the best-looking move now and never revisiting it, and it is safe here because a bigger reach is never a choice you can regret.
Taking the longest stride each time is a different, wrong greedy. It can land you on a zero that a shorter stride would have skipped.

Read the story · Skip to the numbers