All problems

Jump Game III

Medium · graph traversal

You are given an array arr of non-negative integers and a starting index start.

When you stand on index i, you may jump to index i + arr[i] or to index i - arr[i]. You are never allowed to jump outside the array. You may jump as many times as you like, and you may land on the same index more than once.

Return true if you can reach any index whose value is 0, and false otherwise. Standing on a zero at the start counts as reaching it.

Examples

Example 1

Input: arr = [4, 2, 3, 0, 3, 1, 2], start = 5

Output: true

One route is 5 -> 4 -> 1 -> 3, and arr[3] is 0. Another is 5 -> 6 -> 4 -> 1 -> 3.

Example 2

Input: arr = [3, 0, 2, 1, 2], start = 2

Output: false

From index 2 the only indices you can ever stand on are 0, 2, 3 and 4. Index 1, the only zero, is never reached.

Example 3

Input: arr = [1, 1, 0], start = 0

Output: true

Jump 0 -> 1 -> 2, and arr[2] is 0.

Constraints

• 1 <= len(arr) <= 5 * 10^4
• 0 <= arr[i] < len(arr)
• 0 <= start < len(arr)