Furthest reach (jump game)

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You stand on the first cell of [2, 3, 1, 1, 4]. The number on a cell is the furthest you may jump forward from it. What is the fewest jumps to reach the last cell?

By hand you would try routes. 0 → 1 → 4 is two jumps (from cell 1, with a 3, you can reach cell 4). 0 → 2 → 3 → 4 is three. For five cells you can list all routes. For 10,000 cells the routes multiply beyond counting, and even the careful method, "for each cell, the fewest jumps to reach it", looks back at every cell that could have jumped here, which is O(n²) work: about 50 million steps for 10,000 cells.

Build the structure, one piece at a time

There is no data structure here, only two numbers that grow as you scan left to right:

• end: the furthest cell you can stand on with the jumps taken so far. It starts at 0.
• farthest: the furthest cell reachable by one more jump from any cell you have scanned. It starts at 0.

Scan cells from left to right. At cell i, update farthest = max(farthest, i + nums[i]). When i reaches end, you have seen every cell the current jumps can land on, so you must take one more jump, and the best place it can get you is farthest: count a jump and set end = farthest.

1. i = 0: farthest = 0 + 2 = 2. Now i = end, so jump 1; end = 2.
2. i = 1: farthest = max(2, 1 + 3) = 4.
3. i = 2: farthest = max(4, 2 + 1) = 4. Now i = end, so jump 2; end = 4.
4. i = 3: farthest = max(4, 3 + 1) = 4. The last cell, 4, is within end.

Two jumps. Think of end as the right edge of the current "level": every cell up to end costs the same number of jumps, and the next level stretches to the furthest point any cell in this level can reach.

Why it is correct

The invariant: after scanning cell i, every cell up to end is reachable with the jumps counted so far, and farthest is the furthest cell reachable with one more jump. When i reaches end, no cell beyond end is reachable with the current count, because every cell at or before end has been scanned and none reaches further than farthest with its single jump. So one more jump is unavoidable, and taking it as "the whole stretch up to farthest is now reachable" is exact: any cell up to farthest is one jump from some scanned cell. The count is therefore the true minimum, level by level.

level_k+1 right edge = max over i in levels 0..k of ( i + nums[i] )

Why it is fast

Each cell is visited once and does one maximum and one comparison, so the scan is O(n) with two integers of memory. For 10,000 cells that is 10,000 steps instead of 50 million. The reason the O(n²) look-back is unnecessary is that the set of cells reachable in k jumps is always a prefix of the array, so it is fully described by its right edge.

How to recognise it in an interview

Cues: each position gives a reach, intervals that start at a point and extend rightwards, "minimum number of jumps, clips, taps". Say: reachable cells form a prefix, so I only track its right edge and the furthest edge one more step can give. Jump Game asks only whether the last cell is reachable: scan and check that i never passes farthest. Jump Game II is the example. Video Stitching and Minimum Number of Taps to Open to Water a Garden are the same scan after converting each clip or tap into "from this point you can reach that point".

02The idea in one line

Track the furthest index reachable; a new level starts when you pass the current edge.

Reach for it when: Jump game I/II, video stitching, minimum taps to water a garden.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Jump Game II on [2,3,1,1,4]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Scan once; farthest = furthest index reachable so far, end = edge of the current jump
2. i=0: can reach 0+2 = 2, farthest = 2
3. i reached end: take jump 1, new end = farthest = 2
4. i=1: can reach 1+3 = 4, farthest = 4
5. i=2: can reach 2+1 = 3, farthest = 4
6. i reached end: take jump 2, new end = farthest = 4
7. i=3: can reach 3+1 = 4, farthest = 4
8. Index 4 is inside the current jump: 2 jumps (0→1→4)
9. One pass, no DP table: O(n) time, O(1) space

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Greedy: Sort, then take greedily, Reset-on-negative sweep, Last-occurrence partition, Two-pass neighbour constraints, Counting-based greedy (small alphabet), Two-pointer assignment after sorting.