692. Hop to Zero
You stand on a row of stepping stones; stone i shows the number arr[i]. From stone i you may jump exactly arr[i] stones to the right or exactly arr[i] stones to the left, as long as you land on a stone inside the row. You begin on stone start.
Return true if some sequence of jumps lets you stand on a stone that shows 0, and false otherwise. Standing on a zero-stone right at the beginning counts. A stone that shows 0 lets you go nowhere, but you do not need to move from it. Use a visited marker so each stone is processed once, giving O(n) time and space, and avoid deep recursion.
Example 1
- Input:
- arr = [3,1,2,0,4,1,2], start = 5
- Output:
- true
- Explanation:
From stone 5 you hop to stone 4 (5 - 1), then to stone 0 (4 - 4), and finally to stone 3 (0 + 3), which shows 0.
Example 2
- Input:
- arr = [2,2,2,0], start = 0
- Output:
- false
- Explanation:
Starting at stone 0 you can only bounce between stones 0 and 2; the zero on stone 3 is never reachable.
Example 3
- Input:
- arr = [1,3,2,0,1,1,2,4], start = 4
- Output:
- true
- Explanation:
From stone 4 you hop one step left onto stone 3, which shows 0.
Constraints
1 ≤ arr.length ≤ 100000
0 ≤ arr[i] < arr.length
0 ≤ start < arr.length
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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)