Jump Game
Determine if you can reach the last index.
Examples
From index 0 move 1 place to index 1; its value of 3 then reaches the last index.
Every path lands on index 3, whose jump length is 0, so index 4 is never reached.
You start on the last index, so there is nothing to jump.
Problem Understanding
You are given an array nums. nums[i] is the maximum jump length from that position. Return true if you can reach the last index.
Strategy
Track the furthest index reachable so far.
- Start with
reachable = 0— the index you begin on. - Walk
ifrom 0 upward. - If
i > reachable, nothing can land oni: returnfalse. - Otherwise update
reachable = max(reachable, i + nums[i]). - As soon as
reachablereaches the last index, returntrue.
Interactive Visualization
The top row is the jump length at each index; the bottom row marks every index known to be reachable. The marks are always a prefix — which is exactly why one number, the frontier, can stand for all of them. The index being visited is filled, and the furthest cell its jump can land on is outlined.
Try Example 2: every path lands on the 0 at index 3, and the walk stops at index 4, past the frontier.
Dry Run
nums = [2, 3, 1, 1, 4], last index 4:
| i | nums[i] | i > reachable? | i + nums[i] | reachable after |
|---|---|---|---|---|
| 0 | 2 | No (0 ≤ 0) | 2 | 2 |
| 1 | 3 | No (1 ≤ 2) | 4 | 4 |
After index 1 the frontier is 4, which covers the last index — return true without visiting the rest.
Edge Cases & Common Mistakes
Consider these scenarios:
A zero at the start is only fatal if there is more to cross. [0] answers true — you are already at the end — but [0, 1] answers false.
A zero in the middle is only a trap if every path lands on it. In [2, 0, 0] the first jump clears both zeros; in [3, 2, 1, 0, 4] every path is funnelled onto index 3.
Stop as soon as the frontier covers the end. There is no need to visit the rest of the array once the last index is reachable.
Solution
One pass carrying the frontier, stopping early either way — the lines light up as the figure above steps.
Jump Game Code
1var canJump = function(nums) {2 const last = nums.length - 1;3 let reachable = 0;4 for (let i = 0; i < nums.length; i++) {5 if (i > reachable) {6 return false;7 }8 reachable = Math.max(reachable, i + nums[i]);9 if (reachable >= last) {10 return true;11 }12 }13 return true;14};