Google / Amazon Interview Question — LeetCode 1345

In this post, we are going to discuss leetcode 1345 — Jump Game IV, which is recently asked in Google and Amazon interviews.

Problem Analysis

Given an array of integers arr, you are initially positioned at the first index of the array.

Return the minimum number of steps to reach the last index of the array.

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

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404] 
Output: 3 
Explanation: 
You need three jumps from index 0 --> 4 --> 3 --> 9. 
Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7,6,9,6,9,6,9,7] 
Output: 1 
Explanation: 
You can jump directly from index 0 to index 7 which is last index of the array.

This is an array problem, but we need to translate it into a graph and using BFS to approach it.

My Thinking Process

Usually, for questions to find the minimum steps from one state to another state, we can translate the question into a graph problem, and use BFS to approach the problem.

For this specific question, I will translate it into below:

1. For every position n, we can move to the following positions: n+1, n-1, and positions with the same value. This can be treated as a graph, with n as the parent…