Jump Game

Medium#55

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. Can you get to the last cell? Our example: [1, 4, 2, 0, 0, 3, 0, 1] — yes: 0 → 1 → 5 → 7. The zeros at indices 3 and 4 do not matter, as you can jump over them.

55 Jump GameWalkthrough · 1×

Example: [1, 4, 2, 0, 0, 3, 0, 1]. reach is the farthest index known to be reachable; the arc is the longest jump from i.

0114223040536071
not reachable yetreachablecurrent index ipassed, or the goal

The goal is index 7: last = 7

01/27
restart · back · play · step
Speed
1function canJump(nums):
2 last = len(nums) - 1
3 reach = 0
4 for i from 0 to last:
5 if i > reach:
6 return false
7 reach = max(reach, i + nums[i])
8 if reach >= last:
9 return true
state
last
7
reach
–
i
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every index up to reach can be landed on: a jump to reach can be cut short anywhere. So it is enough to keep one number, not a set of cells.
  2. A cell with 0 is a dead end only if nothing jumps past it. Taking the farthest reach of all the cells seen so far keeps you off it whenever you can be.
  3. If i is ever beyond reach, nothing before i jumps that far and nothing after i is reachable at all, so the answer is false. Once reach covers the last index, the answer is true and the rest of the array does not matter.

Complexity

Time O(n): one pass, and it may stop early. Memory O(1): only reach and i.

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.