Jump Game III
01 · Problem
You are given an array of non-negative integers arr and a starting index start. Standing at index i, you may jump either to i + arr[i] or to i - arr[i], as long as the destination stays inside the array (between 0 and arr.length - 1). Jumps that would leave the array are not allowed.
Return true if you can reach any index whose value is 0 (possibly start itself), and false otherwise.
02 · Examples
arr = [4,2,3,0,3,1,2], start = 5
true
From index 5 jump back 1 to index 4, then back 3 to index 1, then forward 2 to index 3, which holds 0.
arr = [4,2,3,0,3,1,2], start = 0
true
From index 0 jump forward 4 to index 4, then back 3 to index 1, then forward 2 to index 3.
arr = [3,0,2,1,2], start = 2
false
From index 2 you can reach indices 0, 4 and 3, but every jump from those lands back on 0, 2, 3 or 4. Index 1, the only 0, is never reached.
03 · Constraints
- 011 <= arr.length <= 5 * 104
- 020 <= arr[i] < arr.length
- 030 <= start < arr.length
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.