Jump Game

Medium · Greedy

You start at index 0 of an array of non-negative integers, where each value tells the maximum number of steps you may jump forward from that position. Determine whether it is possible to reach the last index by chaining such jumps. Return true if some sequence of jumps gets you there, false otherwise.

Examples

Input:  nums = [2,3,1,1,4]
Output: true
Why:    From index 0 jump 1 step to index 1, then jump 3 steps to reach index 4, the last index.

Input:  nums = [3,2,1,0,4]
Output: false
Why:    Every path from index 0 gets stuck at index 3, whose value 0 makes it impossible to move past it, so index 4 is unreachable.

Input:  nums = [0]
Output: true
Why:    You already start at the last index, so no jump is needed.

Constraints

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

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Jump Game

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Jump Game. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.