Greedy The best choice now
491. Jump Game
You are given an array of integers nums. You start at index 0, and nums[i] is the longest jump you can
make from index i. A jump from i can land on any index from i + 1 to i + nums[i], so a jump may be
shorter than nums[i], and a 0 means you cannot move from there.
Return true if you can reach the last index, and false otherwise.
Example 1
Input: nums = [2, 0, 3, 0, 0, 1]
trueExplanation: Jump 2 steps to index 2, then 3 steps to index 5, the last index. A first jump of 1 step would land on the 0 at index 1 and get stuck there.
Example 2
Input: nums = [2, 3, 1, 1, 0, 0, 6]
falseExplanation: No jump from indexes 0 to 3 goes past index 4, and index 4 holds 0. So the 6 at the end is never reached.
Example 3
Input: nums = [0]
trueExplanation: The array has one element, so we start on the last index and need no jump.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1050 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.