141. Jump Game — Reachability
Begin at index zero. From position i, you may jump forward by any distance up to the maximum stored at i; decide whether some sequence of jumps reaches the last position.
The stored length is a maximum, not an obligation to jump exactly that far. A route cannot skip an unreachable section by using a jump from a position never reached.
Example 1
Input
[2,3,1,1,4]
Output
true
Explanation: Reach index 1, then jump to the final index.
Example 2
Input
[3,2,1,0,4]
Output
false
Explanation: The reachable prefix ends at the zero at index 3.
Example 3
Input
[0]
Output
true
Explanation: The starting index already is the target.
Constraints
0 <= nums.length <= 1050 <= nums[i] <= 231 - 1
Hints
Hint 1
Can reachable positions have a hole when every shorter jump is allowed?
Hint 2
Summarize all reachable positions by one frontier.
Hint 3
Fail on a gap; otherwise extend the frontier and stop when it covers the goal.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A blocked frontier
[3,2,1,0,4]
false