Jump Game Iv - Leetcode Solution

Problem Description:

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

In one step you can jump from 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.

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.

Approach:

To solve this problem, we can use a BFS approach, where we start from the first index and keep adding indices to a queue. The queue will initially only contain the first index, and the distance to reach it will be 0. We will keep track of visited indices to avoid revisiting them.

At each step, we will explore all the possible jumps from the current index, which include jumps to indices i+1, i-1 and all indices with the same value as arr[i]. We will add all unvisited indices to the queue, along with their distance (which will be the distance of the current index + 1). The search will continue until we reach the last index of the array.

To optimize the search, we can use a dictionary to keep track of all occurrences of each value in the array and the indices at which they occur. This will help us quickly find all indices we can jump to with a single jump.

Solution:

We start by initializing the queue with the first index and the distance to reach it (0). We also initialize a visited set to keep track of visited indices.

We then create a dictionary to store all the indices where each value in the array occurs.

Next, we enter into a while loop which will continue until the queue is empty (all indices have been visited) or we reach the last index of the array. At each iteration, we get the current index and its distance from the queue. We check if the current index is the last index of the array, and if it is, we return its distance.

Otherwise, we explore all the possible jumps from the current index. For each possible jump, we check if the index is within the bounds of the array and if it has not been previously visited. If both conditions are met, we add the index to the queue along with its distance.

To find all indices with the same value as the current index, we use the dictionary we created earlier to quickly look up all occurrences of the current value in the array. We then add all unvisited indices to the queue along with their distance.

Finally, we mark the current index as visited and continue with the next index in the queue.

If we have exhausted all possible jumps from the current index and have not reached the last index of the array, we return -1 (it is not possible to reach the last index).

Time Complexity:

As we are using BFS, the time complexity will be O(n) where n is the number of elements in the array. Each index will be visited at most once, and each jump from an index can be made in constant time using the dictionary.

Space Complexity:

The space complexity will also be O(n), as we are using a queue to store the indices and a set to keep track of visited indices. We are also using a dictionary to store the occurrences of each value in the array. The maximum size of the dictionary can be O(n) if all values in the array are distinct.

1