Given an array of&nbsp;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:&nbsp;i + 1 &lt; arr.length.
	i - 1 where:&nbsp;i - 1 &gt;= 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.

&nbsp;
Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --&gt; 4 --&gt; 3 --&gt; 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 do not 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.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 5 * 104
	-108 &lt;= arr[i] &lt;= 108


from collections import deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        minSteps = 0
        queue = deque()
        queue.append(0)
        n = len(arr)
        visited = set()
        visited.add(0)
        
		d = {i:[] for i in arr}
        
        for i, val in enumerate(arr):
            d[val].append(i)
        
        while queue:
            for _ in range(len(queue)):
                idx = queue.popleft()
                if idx == n - 1:
                    return minSteps
                
                for i in [*d[arr[idx]], idx - 1, idx + 1]:
                    if i not in visited and 0 <= i < n:
                        visited.add(i)
                        queue.append(i)
                d[arr[idx]].clear()
            minSteps += 1
/*
Here we are using map and queue
map for storing the array elements and where are the other indices of the same element
and queue for BFS

Initially we start with 0 index
So we offer it to the queue
Now until the queue is empty we have to do few things for a given position
i> check the next index (i+1)
ii> check the previous index(i-1)
iii> check all the indices of the list whih are present in the map
once these three things have been done we will
remove the element that is arr[i]
because if we did not remove it we are going to do the same repeated task over and over again
and this will result in stack overflow
so it is important to remove the indices which have been visited once
every time we check the queue we incease the answer because viewing a queue means that
we are not at the last index

I hope the idea was clear :) you'll understand better when you see the code
*/
class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;

        if(n <= 1) return 0;
        Map<Integer, List<Integer>> mp = new HashMap<>();
        for(int i = 0;i < arr.length ; i++) {
            if(!mp.containsKey(arr[i])) {
                mp.put(arr[i],new ArrayList<>());
            }
            List<Integer> ls = mp.get(arr[i]);
            ls.add(i);
        }
        //System.out.print(mp);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int ans = 0;
        while(!q.isEmpty()) {
            ans++;
            int size = q.size();
            for(int i = 0;i < size;i++)
            {
                int j = q.poll();
                //adding j+1
                if(j+1 < n && mp.containsKey(arr[j+1])) {
                    if(j+1 == n-1) return ans;
                    q.offer(j+1);
                }
                //adding j-1
                if(j-1 > 0 && mp.containsKey(arr[j-1])) {
                    q.offer(j-1);
                }

                //adding list indices
                if(mp.containsKey(arr[j])) {
                    for(int k : mp.get(arr[j])) {
                        //if(k == n-1) return ans;
                        if(k != j) {
                             if(k == n-1) return ans;
                            q.offer(k);
                        }
                    }
                    mp.remove(arr[j]);
                }
             }
        }
        return ans;
    }
}
class Solution {
public:
    int minJumps(vector<int>& arr) 
    {
        int n = arr.size();
        unordered_map<int, vector<int>>mp;
        for (int i = 0; i < n; i++) mp[arr[i]].push_back(i);
        
        queue<int>q;
        vector<bool>visited(n, false);
        q.push(0);
        int steps = 0;
        while(!q.empty())
        {
            int size = q.size();
            while(size--)
            {
                int currIdx = q.front();
                q.pop();
                if (currIdx == n - 1) return steps;
                //================================================================
                //EXPLORE ALL POSSIBLE OPTIONS
                if (currIdx + 1 < n && !visited[currIdx + 1])  //OPTION-1 (Move Forward)
                {
                    visited[currIdx + 1] = true;
                    q.push(currIdx + 1);
                }
                if (currIdx - 1 >= 0 && !visited[currIdx - 1]) //OPTION-2 (Move Backward)
                {
                    visited[currIdx - 1] = true;
                    q.push(currIdx - 1);
                }
                for (int newIdx : mp[arr[currIdx]])  //OPTION-3 (Move to same valued idx)
                {                                 //newIdx coud be before currIdx or after currIdx
                    if (!visited[newIdx]) 
                    {
                        visited[newIdx] = true;
                        q.push(newIdx);
                    }
                }
                //===================================================================
                mp[arr[currIdx]].clear();    //EXPLAINED BELOW :)
            }
            steps++;
        }
        return -1;
    }
};
/**
 * @param {number[]} arr
 * @return {number}
 */
var minJumps = function(arr) {
    if(arr.length <= 1) return 0;
    
    const graph = {};
    
    for(let idx = 0; idx < arr.length; idx ++) {
        const num = arr[idx];
        if(graph[num] === undefined) graph[num] = [];
        graph[num].push(idx);
    }
    
    let queue = [];
    const visited = new Set();
    
    queue.push(0);
    visited.add(0);
    
    let steps = 0;
    
    while(queue.length) {
        const nextQueue = [];
        
        for(const idx of queue) {
            if(idx === arr.length - 1) return steps;
            
            const num = arr[idx];
            
            for(const neighbor of graph[num]) {
                if(!visited.has(neighbor)) {
                    visited.add(neighbor);
                    nextQueue.push(neighbor);
                }
            }
            
            if(idx + 1 < arr.length && !visited.has(idx + 1)) {
                visited.add(idx + 1);
                nextQueue.push(idx + 1);
            }
            
            if(idx - 1 >= 0 && !visited.has(idx - 1)) {
                visited.add(idx - 1);
                nextQueue.push(idx - 1);
            }
            
            graph[num].length = 0;
        }
        
        queue = nextQueue;
        steps ++;
    }
    
    return -1;
};
Jump Game IV