573. Can You Reach the End
A hiker walks along a trail of stepping stones numbered 0 to n - 1. The hiker begins on stone 0. The integer jumps[i] is the farthest the hiker can leap forward when standing on stone i; any shorter leap (including a single stone) is also allowed, and a stone with value 0 is a dead end.
Return true if the hiker can land on the last stone, otherwise return false. When there is only one stone the hiker is already at the end, so the answer is true.
The trail can be very long, so aim for a single left-to-right pass: O(n) time and O(1) extra space.
Example 1
- Input:
- jumps = [3,1,0,2,0,1]
- Output:
- true
- Explanation:
Stone 0 leaps to stone 3, which leaps 2 stones to the last stone, so the end is reachable.
Example 2
- Input:
- jumps = [2,1,0,0,1,3]
- Output:
- false
- Explanation:
Stones 0 and 1 can only reach stone 2, which is a dead end, so stone 5 can never be reached.
Example 3
- Input:
- jumps = [1,3,0,0,1]
- Output:
- true
- Explanation:
Stone 0 steps to stone 1, which can leap 3 stones straight onto the last stone.
Constraints
1 ≤ jumps.length ≤ 1000000 ≤ jumps[i] ≤ 100000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)