Amazon Interview Question — LeetCode 1306 — Y Tech

In this post, we are going to discuss leetcode 1306 — Jump Game III, which is recently asked in Amazon interviews.

Problem Analysis

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5 Output: true Explanation: All possible ways to reach at index 3 with value 0 are: index 5 -> index 4 -> index 1 -> index 3 index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0 Output: true Explanation: One possible way to reach at index 3 with value 0 is: index 0 -> index 4 -> index 1 -> index 3

This is a graph problem, which we can solve with BFS or DFS.

My Thinking Process

The question can be translated into a graph problem, where at one position in the array, it can move to at most two other positions, base on the value of the element. So below is the logic towards the approach:

1. Build up the graph from the input array.
2. Loop through the graph with either BFS or DFS (with a visited set), until we reach a node where…