FAANGPrep Sprint
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
✓ = REACHABLE · THE MARKS ARE ALWAYS A PREFIX · OUTLINED = HOW FAR THIS JUMP CAN LAND
START ON INDEX 0
0
1
2
3
4
jump
reach
furthest reachable
0
last index
4
Answer
—
the rule
frontier = the further of itself and i + jump
frontier covers the last index → true
You start on index 0, so the furthest reachable index is 0. The goal is index 4
Next
Visit index 0, which can jump up to 2
nums
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.