Algorithms & Data Structureseasy

Exact Board Jumps I

You are given board, an array of non-negative integers, and a start index. From index i you may move exactly board[i] steps left or right, staying in bounds. Return whether you can reach the last index.

board = [1, 2, 2, 2, 6, 1], start = 0  => true    (0 -> 1 -> 3 -> 5)
board = [3, 1, 1, 1],       start = 0  => true    (0 -> 3)
board = [2, 0, 1, 3],       start = 1  => false   (board[1] = 0 traps you)

Hints

Hint 1

Each index has at most two out-edges: i - board[i] and i + board[i]. That makes this a plain graph search, not DP.

Hint 2

A zero cell is a self-loop — a visited array is what stops it from spinning forever.

Hints

Asked at