Jump Game III
Medium · Stack & Strings · Array · Depth-First Search · Breadth-First Search
Problem
You are given an array arr of non-negative integers and a starting index start. Standing on index i, you may jump to i + arr[i] or to i - arr[i], as long as you land inside the array. You may make as many jumps as you like.
Return true if you can reach any index whose value is 0, and false otherwise.
Examples
Input: arr = [4,2,3,0,3,1,2], start = 5 Output: true
From 5 jump left by 1 to 4, then left by 3 to 1, then right by 2 to 3, where the value is 0.
Input: arr = [3,0,2,1,2], start = 2 Output: false
From 2 you can reach indices 0, 3 and 4, but none of them jumps to index 1, the only zero.
Input: arr = [0,1], start = 0 Output: true
You start on a zero, so no jump is needed.
Constraints
- 1 <= len(arr) <= 5 · 10^4
- 0 <= arr[i] < len(arr)
- 0 <= start < len(arr)
Approaches
- Grow the reachable set until it stops changing — time O(n²), space O(n)
Follow-up
How many jumps does it take to reach the nearest zero? Breadth-first search already answers that: the level at which a zero is first popped is the fewest jumps, because BFS explores positions in order of distance from start.
Related problems
Start free on Cariara · Coding problems · System design studio
