Jump Game
MediumGreedy
You start at index 0 of an array nums. From index i you can jump forward by any number of steps from 1 up to nums[i]; a 0 means you cannot move from there.
Return true if you can reach the last index, and false otherwise.
Examples
Input: nums = [1, 3, 0, 0, 2] Output: true
Jump 1 to index 1, then 3 to index 4, the last one.
Input: nums = [2, 1, 0, 3] Output: false
Every route lands on index 2, whose 0 lets you go no further.
Constraints
1 ≤ nums.length ≤ 10⁴0 ≤ nums[i] ≤ 10⁵
Stuck?
Hint 1
You do not need to try every route. Track the furthest index you can reach from anything you have reached so far.
Hint 2
Walk the array. If the index you are on is beyond the furthest reach, you are stuck; otherwise stretch the reach to i + nums[i]. Stop once the reach covers the last index.
The idea
The indexes you can reach always form an unbroken stretch from index 0, because a jump can stop at any distance up to its length. So only the far end of that stretch matters. Walk the array, and let every index inside the stretch push the far end out to i + nums[i].
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
reach is the furthest index known to be reachable. At the start that is index 0, where you stand.
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;}The trap
Always taking the longest jump from where you stand feels like the best way to get far, and it works when no 0 is in the way. But the longest jump can land on a 0, while a shorter jump from the same index lands somewhere that goes further. Arrays like that get false even though a route to the end exists.
function canJump(nums) { let i = 0; while (i < nums.length - 1) { if (nums[i] === 0) return false; i += nums[i]; // always takes the longest jump } return true;}