Jump Game

MediumArray Greedy Dynamic Programming

In a platform game, the hero starts on platform 0 of a row of platforms. Platform i has a spring of strength nums[i]: from there the hero can jump forward by any number of platforms from 1 up to nums[i]. A spring of strength 0 is broken, and the hero cannot jump from that platform at all.

Return true if the hero can reach the last platform, and false otherwise.

Example 1

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

Explanation: Jump from platform 0 to 2, then from 2 straight to 4, skipping both broken springs.

Example 2

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

Explanation: Platforms 0 and 1 only reach platform 2, whose spring is broken, so platform 3 is out of reach.

Example 3

Input: nums = [5]
Output: true

Explanation: The hero already stands on the last platform.

Constraints

There are between 1 and 10^4 platforms.
Each spring strength is an integer from 0 to 10^5.

Follow-up: If the last platform is always reachable, what is the fewest number of jumps that gets the hero 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