Jump Game IV

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.

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.

Constraints:

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

Solution:

This is a hard leetcode question. To be honest, I wasn’t able to solve it on my own and had to take help of friends and some editorials. But now I think it is perfectly clear to me how to solve this. So lets go.

It says we can jump from index i to:
: i+1, if it is in the bounds of array
: i -1, if it is in the bounds of array
: j, where arr[i] == arr[j] and i != j

So we see this an exploration problem and we have to return the minimum number of steps to reach the last index. Since minimum index is required, we can explore all possible scenarios using breadth first search where each level will act as one step. This is like the main thing to know while using BFS. Each level acts as one step. And since all scenarios for one step is explored at the first level, we can be sure the answer we get is correct. Now, moving to i+1 and i-1 is easy, just go one index forward and backward if it is in the bounds of array. But getting to j is not straightforward. We can always traverse array to get at which index arr[i] == arr[j], but that is time consuming. So we’ll create a dictionary, a hashmap to store all indexes of arr[i] == arr[j], that is indexes of same elements in the array. In the example,for aray = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404] , hashmap will be {100: [0, 3], -23: [1, 2], 404: [3, 9], 23: [5, 6, 7], 3: [8]}.

Now we can find indexes for all 3 conditions in O(1) time. We’ll start with node 0, as constraints say we will have at least one element. We will maintain a visited set to not visit the already visited indexes. Also a variable step is maintained to store number of steps and since each level in BFS means one step, jump is updated when one level is fully completed. And for not making redundant searches, we’ll also remove the elements from the map as soon as we use it. Lets see the code:

from collections import deque
def minJumps(self, arr: List[int]) -> int:
    hash_map = {} // indexes of same element in array
    for i in range(len(arr)):
        if arr[i] not in hash_map:
            hash_map[arr[i]] = []
        hash_map[arr[i]].append(i)
    visited = {0} # maintain nodes visited
    q = deque()
    q.append(0) #it will maintain all nodes in one level
    steps = 0
    while q:
        nx = deque() # at each level, we will create the queue for next level by adding all legal elements we get from 3 conditions.
        for node in q:
            if node == len(arr) - 1: return steps
            back = node - 1
            front = node + 1
            if 0 <= back < len(arr) and back not in visited:
                nx.append(back)
                visited.add(back)
            if 0 <= front < len(arr) and front not in visited:
                visited.add(front)
                nx.append(front)
            for same_node in hash_map[arr[node]]:
                if same_node not in visited:
                    visited.add(same_node)
                    nx.append(same_node)
            hash_map[arr[node]].clear()
            q = nx
        steps += 1
    return -1

It’s pretty simple after we get the details. First we create a hashmap, then we create the first level manually as [0]. Traverse all elements in the current level and for each node in the level, try all the 3 conditions. Check if we can move to i+1 or to i-1. And then check if we can move to same element’s indexes in the array. Since we have traversed all same elements for ex-> like we have traversed all the 100s present in the array, so we clear that array to reduce redundancy. And then keep on traversing until we get node == i-1 which is the answer and we return the steps, that is the levels.

Thanks.