Bounce to a Zero

Medium

You get an array of non-negative integers hops and a starting cell start. Standing on cell i, you can hop exactly hops[i] cells to the left or exactly hops[i] cells to the right, landing on i - hops[i] or i + hops[i]. You may never hop outside the array. Return True if, starting from start, you can land on some cell that holds 0, and False otherwise.

Example 1

hops=[3, 1, 2, 0, 4, 1], start=5 → True

The path is 5 → 4 → 0 → 3: from cell 5 hop 1 left, from 4 hop 4 left, from 0 hop 3 right, and cell 3 holds a zero.

Example 2

hops=[1, 2, 0, 2, 1], start=3 → False

Cell 3 leads only to cell 1, and cell 1 leads only back to 3. The zero in cell 2 is out of reach.

Example 3

hops=[0], start=0 → True

We are already standing on a zero.

Constraints

1 ≤ len(hops) ≤ 5·10⁴
0 ≤ hops[i] < len(hops)
0 ≤ start < len(hops)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Array

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Ratio Chain Queries Medium Rain Reaching Both Seas Medium Can the Ball Stop at the Target Medium

Input

hops=[3, 1, 2, 0, 4, 1], start=5

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.