<p>Given an array of&nbsp;integers <code>arr</code>, you are initially positioned at the first index of the array.</p>

<p>In one step you can jump from index <code>i</code> to index:</p>

<ul>
	<li><code>i + 1</code> where:&nbsp;<code>i + 1 &lt; arr.length</code>.</li>
	<li><code>i - 1</code> where:&nbsp;<code>i - 1 &gt;= 0</code>.</li>
	<li><code>j</code> where: <code>arr[i] == arr[j]</code> and <code>i != j</code>.</li>
</ul>

<p>Return <em>the minimum number of steps</em> to reach the <strong>last index</strong> of the array.</p>

<p>Notice that you can not jump outside of the array at any time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [7]
<strong>Output:</strong> 0
<strong>Explanation:</strong> Start index is the last index. You do not need to jump.
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-10<sup>8</sup> &lt;= arr[i] &lt;= 10<sup>8</sup></code></li>
</ul>

from collections import defaultdict

class Solution:
    def minJumps(self, arr: List[int]) -> int:
    
        # convert this to a graph question with bi-directional edges
        # employ BFS
        n = len(arr)
        
        occ = defaultdict(list)
        
        for i, num in list(enumerate(arr)):
            occ[num].append(i)
    
        # we need to keep track of the number of steps, thus we can either use recursion, or an obj/arr
        # [steps, idx]
        queue = [[0, 0]]
        
        # we update and set visited at enumerate since we're using a queue
        visited = [False]*n
        visited[0] = True
        
        while len(queue) > 0:
            curr = queue.pop(0)
            
            if curr[1] == n-1:
                return curr[0]
            
            if curr[1] < n-1 and not visited[curr[1] + 1]:
                queue.append([curr[0] + 1, curr[1] + 1])
                visited[curr[1]+1] = True
                    
            if curr[1] > 1 and not visited[curr[1]-1]:
                queue.append([curr[0] + 1, curr[1] - 1])
                visited[curr[1]-1] = True
                
            for nbr in occ[arr[curr[1]]]:
                if not visited[nbr]:
                    visited[nbr] = True
                    queue.append([curr[0] + 1, nbr])
                    
            del occ[arr[curr[1]]]
            
        return n-1


# from collections import defaultdict

# class Solution:
#     def minJumps(self, arr: List[int]) -> int:
    
#         # convert this to a graph question with bi-directional edges
#         # employ BFS
#         n = len(arr)
        
#         adjList = defaultdict(set)
#         last = defaultdict(lambda : -1)
        
#         for i, num in enumerate(arr):
#             latest = last[num]
#             if latest != -1:
#                 adjList[i].add(latest)
#                 adjList[latest].add(i)
#                 for nbr in adjList[latest]:
#                     adjList[nbr].add(i)
#                     adjList[i].add(nbr)
#             last[num] = i
        
    
#         for i in range(n-1):
#             adjList[i].add(i+1)
#             adjList[n-1-i].add(n-2-i)
    
#         # we need to keep track of the number of steps, thus we can either use recursion, or an obj/arr
#         # [steps, idx]
#         queue = [[0, 0]]
        
#         # we update and set visited at enumerate since we're using a queue
#         visited = [False]*n
#         visited[0] = True
        
#         while len(queue) > 0:
            
#             curr = queue.pop(0)
        
#             if curr[1] == n-1:
#                 return curr[0]
            
#             for nbr in adjList[curr[1]]:
#                 if not visited[nbr]:
#                     visited[nbr] = True
#                     queue.append([curr[0] + 1, nbr])
                    
#         return n-1

1370