Jump Game | Problems

You start at index 0 of an array, where each value tells you the farthest you're allowed to jump forward from that position. Decide whether it's possible to chain jumps together and land on the final index, returning true if so and false if you'd get stuck short of it.

Input Format

Implement canJump(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.

Output Format

Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input

nums = [2,3,1,1,4]

Output

true

Example 2

Input

nums = [3,2,1,0,4]

Output

false

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

Test Cases (2)

Case 1

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

Case 2

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

Topics

Array Two Pointers

Iterate through the array while maintaining the farthest index you can reach. If you ever land on an index beyond your current reach, return false. Otherwise, update your reach as max(maxReach, i + nums[i]).

javascript

function canJump(nums) {
  let maxReach = 0;

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

  return true;
}

Time: O(n) Space: O(1)

Saved in this browser only. Private to you.