59. Jump Game

MediumArray Greedy Dynamic Programming

You start at index 0 of an array nums of non-negative integers. The value nums[i] is the maximum distance you may jump forward from index i (any jump from 1 up to nums[i] is allowed; a value of 0 means you cannot move from there).

Return true if you can reach the last index, and false otherwise.

Example 1

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

Explanation: Jump 0 → 1, then 1 → 3 (skipping the 0), then 3 → 4.

Example 2

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

Explanation: Indices 0 and 1 can reach at most index 2, and index 2 has jump length 0, so index 3 is out of reach.

Example 3

Input: nums = [0]
Output: true

Explanation: You already stand on the last index.

Constraints

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

Follow-up: If the end is always reachable, what is the minimum number of jumps needed to get there?

💡 Hint 1

You never need to know the exact path, only how far to the right you could possibly get.

💡 Hint 2

Scan left to right while tracking reach, the furthest index reachable so far. If the current index is beyond reach, you are stuck.

💡 Hint 3

Otherwise update reach = max(reach, i + nums[i]) and stop early once it covers the last index.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Greedy reach. Every index up to the furthest reachable index is itself reachable (you can always take a shorter jump), so a single number reach describes the whole reachable region. Scan left to right: if i > reach, index i can never be reached and neither can the end, so return false. Otherwise extend reach to max(reach, i + nums[i]) and return true as soon as it reaches the last index.

Time O(n)Space O(1)

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]);
    if (reach >= nums.length - 1) return true;
  }
  return true;
}

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false;
            reach = Math.max(reach, i + nums[i]);
            if (reach >= nums.length - 1) return true;
        }
        return true;
    }
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function canJump(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit