Jump Game II

Medium#45

You stand on the first cell of an array. Each number is the longest jump you may make from its cell; any shorter jump is fine too. The last cell can surely be reached. In how few jumps? Our example: [2, 4, 1, 2, 3, 1, 1, 0] — 3 jumps: 0 → 1 → 4 → 7. Two are not enough: after two jumps you get no farther than index 5.

45 Jump Game IIWalkthrough · 1×

Example: [2, 4, 1, 2, 3, 1, 1, 0]. end is the farthest index the jumps so far reach, far — the farthest one more jump reaches. The arc in the colour of i is its longest jump; the arc in the other colour is the jump counted when i reaches end.

0214213243516170
not reachable yetreached in jumps jumpsone more jump awaycurrent index ipassed, or the goal

No jumps yet

01/32
restart · back · play · step
Speed
1function jump(nums):
2 jumps = 0
3 end = 0 // how far the jumps so far reach
4 far = 0 // how far one more jump reaches
5 for i from 0 to len(nums) - 2:
6 far = max(far, i + nums[i])
7 if i == end:
8 jumps = jumps + 1
9 end = far
10 return jumps
state
jumps
0
end
–
far
–
i
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The cells up to end are exactly those reachable in jumps jumps, and the cells after end up to far need one more. The run walks over the array range by range, like a breadth-first search, but without a queue.
  2. Which cell the next jump starts from is decided only when i reaches end: by then every cell of the range has been seen, and far is the farthest of their jumps. Nothing is chosen before all the options are known.
  3. The loop stops before the last index: landing on it ends the trip, and counting a jump from there would add one too many.

Complexity

Time O(n): one pass over the array. Memory O(1): only jumps, end and far.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.