Can you hop from the first index to the last? Walk once, keeping the farthest spot you can reach; if you ever stand past it, you're stuck.
▼The problem
LeetCode 55 (Medium). nums[i] is the maximum jump length from index i. Starting at index 0, return true if you can reach the last index.
Examples: [2, 3, 1, 1, 4] → true (0 → 1, then a jump of 3 to the end); [3, 2, 1, 0, 4] → false (every path lands on index 3, whose 0 goes nowhere).
The solution
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False # stuck
farthest = max(farthest, i + jump)
if farthest >= len(nums) - 1:
return True # covers the end
return TrueTranscript
Jump Game. Each number is the farthest you can jump from that spot. Start at the first index: can you reach the last?
Take two, three, one, one, four. Hop from the two to the three, then jump three to the end. True. Now take three, two, one, zero, four. Every path lands on the zero, and zero goes nowhere. False.
You could try every jump from every spot, but that branches fast. Exponential time, or n squared even if you remember which spots work.
The greedy trick: don't choose jumps at all. Just track the farthest index you can reach. Walk left to right. While you stand inside your reach, stretch it to i plus the jump, if that's farther. If you ever step past the reach, you're stuck.
In code, farthest starts at zero. For each index, if i is past farthest, return false. Otherwise update farthest. Once it covers the last index, return true.
First example. Index zero reaches two. Index one adds three: reach four, the last index. True, after two steps.
Now the trap. Index zero reaches three. Index one: one plus two, still three. Index two: still three. Index three is the zero: still three. Index four is past the reach. Stuck. False.
One pass, and one number to remember. So the time is O of n, and the space is constant.
Don't plan the jumps. Just stretch the reach. That's Jump Game.