Jump Game

Difficulty: Medium

You start at index 0 of an array of numbers. The number at each index tells you the maximum number of steps you're allowed to jump forward from that index (you can jump anywhere from 1 up to that many steps, or stay put by not jumping at all if you don't need to).

Determine whether you can reach the last index of the array, starting from index 0.

Examples

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

Jump 1 step from index 0 to index 1, then 3 steps to the last index.

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

No matter how you jump, you always land on index 3, whose value is 0, so you get stuck there and can never reach index 4.

Input: nums = [0]
Output: true

You're already standing on the last index.

Constraints

  • 1 <= nums.length <= 10^4

  • 0 <= nums[i] <= 10^5

Approach

Trying every combination of jump lengths explodes combinatorially. Instead, notice that all you actually need to know at any position is the single furthest index reachable so far from everything to its left - not which specific jumps got you there.

Greedily scan left to right, keeping a running "furthest reach". At each index i, if i is beyond the furthest reach, you could never have gotten here, so it's unreachable and the whole thing fails. Otherwise, update the furthest reach to max(furthest, i + nums[i]). If the furthest reach ever covers the last index, you're done.

Solutions

Brute Force - Try Every Jump (Recursion)

From each index, recursively try every possible jump length and see if any path reaches the end.

function canJump(nums) {
  function canReachEnd(pos) {
    if (pos >= nums.length - 1) return true;
    const maxJump = Math.min(nums[pos], nums.length - 1 - pos);
    for (let step = 1; step <= maxJump; step++) {
      if (canReachEnd(pos + step)) return true;
    }
    return false;
  }
  return canReachEnd(0);
}

Time: O(2^n) in the worst case, since each position branches into many jump choices · Space: O(n) recursion depth

Optimal - Greedy Furthest Reach

Track the furthest index reachable so far while scanning left to right. If the current index ever exceeds that reach, the end is unreachable.

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

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