Jump Game

Medium

Problem

You start at index 0. nums[i] is the maximum jump length from index i. Return true if you can reach the last index.

Example 1

Input:  [2, 3, 1, 1, 4]
Output: true

Example 2

Input:  [3, 2, 1, 0, 4]
Output: false

Every route lands on index 3, which has jump length 0.

Test cases

Case 1

Input:    [2,3,1,1,4]
Expected: true

Case 2

Input:    [3,2,1,0,4]
Expected: false

Case 3

Input:    [0]
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Track the furthest reachable index

Time O(n)Space O(1)

If the current index is beyond the furthest reach, you are stuck; otherwise extend the reach.

function canJump(nums) {
let reach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > reach) return false;
reach = Math.max(reach, i + nums[i]);
}
return true;
}