Microsoft Online Assessment (OA) - Jump Game

You are given an array of non-negative integers arr and a start index. When you are at an index i, you can move left or right by arr[i]. Your task is to figure out if you can reach value 0.

Example 1:

Input: arr = [3, 4, 2, 3, 0, 3, 1, 2, 1], start = 7
Output: true
Explanation:

left -> left -> right

Example 2:

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

Try it yourself

Implementation

1from collections import deque
2from typing import List
3
4def jump_game(arr: List[int], start: int) -> bool:
5    seen = set()
6    queue = deque([start])
7    while queue:
8        size = len(queue)
9        for i in range(size):
10            cur = queue.popleft()
11            if arr[cur] == 0: return True
12            if cur in seen: continue
13            seen.add(cur)
14            if cur + arr[cur] < len(arr): queue.append(cur + arr[cur])
15            if cur - arr[cur] >= 0: queue.append(cur - arr[cur])
16    return False
17
18if __name__ == '__main__':
19    arr = [int(x) for x in input().split()]
20    start = int(input())
21    res = jump_game(arr, start)
22    print('true' if res else 'false')
23