<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>

class Solution:
    def getNeighbors(self, nums, i, fullyConnectedNodes):
        """
        We return all the neighbors, which includes the indexes to where we can jump
        directly and the 2 adjacent nodes.
        Notice that we could add the adjacent indexes twice if they are also included
        in the nodes that we can jump directly too, this should be okay since the caller
        should check for "seen" nodes. Also, notice that the indexes in fullyConnectedNodes
        groups are sorted by index asc, and we add the adjacent indexes at the end which can
        break this sorting, but we don't use this sorting since it doesn't change the runtime.
        Although, there are cases where it would help, such as:

        [1,1,1,1,1,1,2]
         0 1 2 3 4 5 6

        If we process the index 5 early, we can see that it neighbors with the last index and we
        don't need to process all the other indexes. Even if we add the adjacent indexes at the
        end, we would process it second (since index 0 has only 1 adjancent index, otherwise it would be
        third) which is not bad.
        """
        neighbors = []
        neighbors.extend(fullyConnectedNodes[nums[i]])

        if i > 0:
            neighbors.append(i-1)

        # This check shouldn't be needed, because the only case where this could
        # happen is for the last index, but when we find the last index, we finish
        # the algorigthm since it's the solution, but adding it anyways for 
        # correctness to not depend on how the caller is implemented.
        if i < len(nums)-1:
            neighbors.append(i+1)

        return neighbors
    
    def minJumps(self, arr: List[int]) -> int:
        """
        I coded exactly the same solution as the editorial, the only difference is
        that I didn't realize that we can clear the groups of fully connected nodes
        once all the nodes are added. This is an optimization on top of the "seen" 
        nodes, which is an optimization on top of "visited" nodes.

        - Visited: each node can be added multiple times to the queue if there are
          several nodes at the same level that neighbor with it, but when it is
          popped again after the first time, it will be discarded.
        - Seen: each node is added once to the queue, if other node at the same level
          neighbors with it, it will not be added to the queue again. So this prevents
          duplicates in the queue and having to pop the same node many times.
        - Removing links: after adding all neighbors to queue, remove all links between
          each other. Notice that the nature of this graph makes this optimization possible
          since all the positions with same value, are all neighbors of each other. So once
          you get to 1 of them, from that one you can reach all the others, so if you remove
          all the edges, you don't need to iterate over all those edges and test if the
          neighbor is in the "seen". Notice that fullyConnectedNodes is not an adjacency list, it
          just stores groups of nodes that are fully connected. If we can created these groups
          in other graphs, we can apply this technique as well.
        """
        if len(arr) == 1:
            return 0

        fullyConnectedNodes = collections.defaultdict(list)
        for i,n in enumerate(arr):
            fullyConnectedNodes[n].append(i)

        level = 0
        seen = set([0])
        bfs = deque([0])
        while bfs:
            levelSize = len(bfs)
            for i in range(levelSize):
                currentIndex = bfs.popleft()
                neighbors = self.getNeighbors(arr, currentIndex, fullyConnectedNodes)
                for neighborIndex in neighbors:
                    if neighborIndex not in seen:
                        if neighborIndex == len(arr)-1:
                            return level + 1

                        seen.add(neighborIndex)
                        bfs.append(neighborIndex)

                fullyConnectedNodes[arr[currentIndex]].clear()
            
            level += 1

        # Added for completeness, there is always a solution since worse case, just advance one
        # step at at time.
        return -1

27951