Jump Game
You stand on the first position of a list. The number at each position is the longest jump you can make from there. You may jump any distance up to that number, including a shorter one.
Return true if you can reach the last position, or false if you will always get stuck before it.
Examples
Input nums = [2, 3, 1, 1, 4]
Output true
Jump 1 to position 1, then 3 to the end.
Input nums = [3, 2, 1, 0, 4]
Output false
Every route ends on the zero at position 3.
Input nums = [0]
Output true
You are already at the last position.
Constraints
- 1 <= nums.length <= 10,000
- 0 <= nums[i] <= 100,000
Stuck? Take one hint at a time
Common mistakes
- Searching all paths with recursion, which is exponential.
- Forgetting to stop when i is past farthest.
- Treating the number as a fixed jump instead of a maximum.
- Special-casing lists of length 1 incorrectly.
Questions an interviewer may ask next
- Return the minimum number of jumps needed to reach the end. (Track the current and next reach.)
- You may also jump backward by the same amounts. How does the problem change?
- Return one actual sequence of jumps that reaches the end.
- Prove the greedy choice is safe.
How often this is reported
Commonly reported across 11 of 25 tracked companies
11/25
Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.
nums
[2,3,1,1,4]
Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.