Jump Game.

Photo by Mika Baumeister on Unsplash

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

In one step you can jump from an index i to index:

• i + 1 where: i + 1 < arr.length.
• i - 1 where: i - 1 >= 0.
• j where: arr[i] == arr[j] and i != j.

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]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:

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.

Example 4:

Input: arr = [6,1,9]
Output: 2

Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Constraints:

• 1 <= arr.length <= 5 * 104
• -108 <= arr[i] <= 108

• One can jump from step i to step i + 1, where i + 1 < n.
• One can jump from step i to step i - 1, where i - 1 >= 0.
• One can jump from step i to step j, where k[i] == k[j] and i != j.

For example, consider the following mini-game and its solution:

In the example given above, four jumps are needed to reach the end. The k array for this example will be ,[2, 5, 7, 5, 3, 4] and your function should return 4 as output.

Solution

This problem can be mapped as a graph problem in which we need to find the shortest path between two vertices. So, to solve this problem, we will use a breadth-first search.

• First, we will build a graph. This will be an unweighted, undirected graph, and the indices of k will represent nodes.
• There will be an edge between the nodes corresponding to the surrounding indices and also to the other indices that have the same value. We will store nodes with the same value together in a graph hash table.
• Now, we will do a breadth-first search and find all paths from the first index to the last.
• However, if we already checked one index, we do not need to check it again. We can mark the index as visited by storing it in a visited set.
• While searching, we do not need to iterate the whole list to find the nodes with the same value as the next steps, we need to consult the precomputed graph hash table. However, to prevent retracing our own steps, we need to clear the corresponding hash table entry once we reach a specific node.

Time complexity

The time complexity will be O(n) because we visit every node at most once.

Space complexity

The space complexity will be O(n) because we store nodes in the hash.

If you like the content please follow me here @medium and at LinkedIn

https://www.linkedin.com/in/jaydeep-shil-75a90847