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.

Example 2:
Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't 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.

Example 4:
Input: arr = [6,1,9]
Output: 2

Example 5:
Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

 
Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Difficulty: interview

Starter code:

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        

Solutions:
from collections import deque

class Solution:
    def minJumps(self, arr: list) -> int:
        if len(arr) == 1:
            return 0
        graph = {}
        for i, n in enumerate(arr):
            if n in graph:
                graph[n].append(i)
            else:
                graph[n] = [i]
        
        curs = [0]
        other = [len(arr)-1]
        visited = {0}
        visited2 = {len(arr)-1}
        step = 0
        while curs:
            if len(curs) > len(other):
                curs, other = other, curs
                visited, visited2 = visited2, visited
            nex = []
            for node in curs:
                for child in graph[arr[node]]:
                    if child in visited2:
                        return step + 1
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                for child in [node-1, node+1]:
                    if child in visited2:
                        return step + 1
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)
            curs = nex
            step += 1
        return -1
                    
                    
            
            


from collections import deque

class Solution:
    def minJumps(self, arr: list) -> int:
        if len(arr) == 1:
            return 0
        graph = {}
        for i, n in enumerate(arr):
            if n in graph:
                graph[n].append(i)
            else:
                graph[n] = [i]
        
        curs = [0]
        other = [len(arr)-1]
        visited = {0}
        visited2 = {len(arr)-1}
        step = 0
        while curs:
            is_curs = len(curs) <= len(other)
            if not is_curs:
                curs, other = other, curs
                visited, visited2 = visited2, visited
            nex = []

            for node in curs:
                for child in graph[arr[node]]:
                    if child in visited2:
                        return step + 1
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                for child in [node-1, node+1]:
                    if child in visited2:
                        return step + 1
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)
            curs = nex
            step += 1
        return -1
                    
                    
            
            


class Solution:
    # bidirectional, best 416 ms, memory 99.90%
    def minJumps(self, arr):
        length = len(arr)
        # if no any connection in nodes, answer equals to array length - 1
        if len(set(arr)) == length: return length - 1
        if arr[0] == arr[-1]: return 1

        _map = defaultdict(set) # connection map
        for i, val in enumerate(arr): _map[val].add(i)

        # BFS, seen: visited index, visit: visited connection
        res, seen, visit = 0, {0}, set()
        # curs: nodes in current side level, other: nodes in opposite side
        curs, other = {0}, {length - 1}
        while curs:
            res += 1
            # store found nodes in this level
            thisLevel = set()
            for i in curs:
                # check move backwards 
                if i - 1 > 0 and i - 1 not in seen: 
                    thisLevel.add(i - 1)
                # check in place
                if arr[i] in _map:
                    thisLevel |= (_map[arr[i]] - seen) 
                    visit.add(arr[i])
                    del _map[arr[i]]
                # check move forwards
                if i + 1 < length and i + 1 not in seen: 
                    thisLevel.add(i + 1)

            # check if this level and the other side intersect
            if thisLevel & other: return res  

            # update current side for next round          
            curs = thisLevel
            # choose smaller side into next round 
            if len(curs) > len(other): curs, other = other, curs
            # if we don't exchange, put found nodes into seen
            # because they are found in current direction
            else: seen |= thisLevel

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        connected = collections.defaultdict(list)
        _ = [connected[v].append(i) for i, v in enumerate(arr)]
        
        queue, pos_visited = [0], set([0])
        steps = 0
        
        while queue:
            next_steps = []
            for cur_pos in queue:
                if cur_pos == len(arr) - 1: return steps
                next_steps += [cur_pos - 1, cur_pos + 1] + connected[arr[cur_pos]]
                connected[arr[cur_pos]].clear()
            queue = []
            for _ in next_steps:
                if _ >= 0 and _ < len(arr) and _ not in pos_visited:
                    queue.append(_)
                    pos_visited.add(_)
            steps += 1
        return steps
                


class Solution:
    def minJumps(self, arr):
        n = len(arr)
        if n == 1: return 0 
        d = defaultdict(list)
        for i,val in enumerate(arr):
            d[val].append(i)
        visited = set([0])
        stack = deque([0])
        k, jumps = len(stack), 1
        while stack:
            i = stack.popleft()
            childs = [j for j in [i-1,i+1] if arr[j] != arr[i]] + [j for j in d.pop(arr[i],[])]
            childs = [j for j in childs if 0 <= j < n and j not in visited]
            for j in childs:
                if j == n-1: return jumps
                visited.add(j)
                stack.append(j)
            k -= 1
            if not k:
                k = len(stack)
                jumps += 1
        return jumps

from collections import defaultdict
class Solution:
    def get_jump_indices(self, arr):
        jump_indices = defaultdict(set)
        for i, val in enumerate(arr):
            jump_indices[val].add(i)
        return jump_indices
    def minJumps(self, arr: List[int]) -> int:
        # Dictionary from array value to set of jumpable indices
        jump_indices = self.get_jump_indices(arr)
        next_indices = [len(arr) - 1]
        visited = set()
        visited.add(len(arr) - 1)
        jumps = 0
        while next_indices:
            reachable_indices_set = set()
            for index in next_indices:
                if index == 0:
                    return jumps
                reachable_indices = jump_indices[arr[index]].copy()
                reachable_indices.remove(index)
                reachable_indices.add(index - 1)
                if index != len(arr) - 1:
                    reachable_indices.add(index + 1)
                for reachable_index in reachable_indices:
                    if reachable_index in visited:
                        continue
                    visited.add(reachable_index)
                    reachable_indices_set.add(reachable_index)
            next_indices = list(reachable_indices_set)
            jumps += 1
        return None

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        v2n = collections.defaultdict(set)
        for i, v in enumerate(arr):
            if 0 < i < len(arr) - 1 and arr[i - 1] == v and arr[i + 1] == v:
                continue
            v2n[v].add(i)
        visited, seen, q, step = set([0]), set(), collections.deque([0]), 0
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur == len(arr) - 1: return step
                neighbors = set([cur + 1, cur - 1] + [x for x in v2n[arr[cur]]])
                for nb in neighbors:
                    if nb >= 0 and nb < len(arr) and nb != cur and nb not in visited:
                        visited.add(cur)
                        q.append(nb)
                # seen.add(cur)
            step += 1
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr or len(arr)==1:
            return 0
        
        dp=[float('inf')]*len(arr)
        dp[0]=0
        
        position=collections.defaultdict(set)
        visited={}
        for i,e in enumerate(arr):
            position[e].add(i)
            visited[i]=False
        visited[0]=True
        
        start={0}
        step=0
        while start:
            nextstart=set()
            for i in start:
                
                if i==len(arr)-1:
                    return step
                
                if i-1>=0 and not visited[i-1]:
                    dp[i-1]=min(dp[i-1],dp[i]+1)
                    nextstart.add(i-1)
                    visited[i-1]=True
                if i+1<len(arr) and not visited[i+1]:
                    dp[i+1]=min(dp[i+1],dp[i]+1)
                    nextstart.add(i+1)
                    visited[i+1]=True
                for p in position[arr[i]]:
                    if p!=i and not visited[p]:
                        dp[p]=min(dp[p],dp[i]+1)
                        nextstart.add(p)
                        visited[p]=True
                position[arr[i]].clear()

            start=nextstart
            step+=1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
  
        
        
        val_to_ids = collections.defaultdict(list)
        _ = [val_to_ids[x].append(i) for i, x in enumerate(arr)]
        
        # print(val_to_ids)
        queue = collections.deque([(0, 0)])
        positions_seen = set()
        num_met = set()
        while queue:
            i, dis = queue.popleft()
            if i == len(arr) - 1:
                return dis
            val = arr[i]
            positions_seen.add(i)
            
            possible_indexes = []
            possible_indexes.append(i + 1)
            possible_indexes.append(i - 1)
            
            if len(val_to_ids[val]) > 1:
                for idx in val_to_ids[val]:
                    if idx not in positions_seen:
                        possible_indexes.append(idx)
                del val_to_ids[val]

            for p in possible_indexes:
                if p < 0 or p > len(arr) or p in positions_seen:
                    continue
                queue.append((p, dis+1))
            

        
#         nei = collections.defaultdict(list)
#         _ = [nei[x].append(i) for i, x in enumerate(arr)]

#         frontier = collections.deque([(0,0)])
#         num_met, pos_met = set(), set()
#         while frontier:
#             pos, step = frontier.popleft() # state: position, step
#             if pos == len(arr) - 1: return step
#             num = arr[pos]
#             pos_met.add(pos) # track explored positions

#             for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
#                 if p in pos_met or not 0 <= p < len(arr): continue
#                 frontier.append((p, step + 1))

#             num_met.add(num) # track explored values


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # corner case
        if len(arr) == 1:
            return 0
        
        # create a better lookup data structure
        dict_ = collections.defaultdict(list)
        for index in range(len(arr)):
            dict_[arr[index]].append(index)
        
        #print(dict_)
            
        # a variable to save ans
        min_count = 0
        
        # remember visited points
        visited = set()
        visited.add((arr[0], 0))
        
        # bfs
        queue = collections.deque()
        queue.append((arr[0], 0))
        
        while queue:
            #print(queue)
            size = len(queue)
            # spread the nodes at the same level
            for i in range(size):
                curr_num, index = queue.popleft()
                #print(\"index: \",index)
                # reach the condition 
                if index == len(arr) - 1:
                    return min_count
                # add unvisited neighbor points to the queue
                for new_num, new_index in self.move(curr_num, index, arr, dict_,visited):
                    if (new_num, new_index) not in visited:
                        #print(\"new_index: \", new_index)
                        visited.add((new_num,new_index))
                        queue.append((new_num, new_index))                                 
            min_count = min_count + 1
        
    
    def move(self, curr_num, index, arr, dict_, visited):
            for new_num, new_index in [(arr[index - 1], index - 1), (arr[index+1], index + 1)]:
                if 0 <= new_index < len(arr) and (new_num, new_index) not in visited:
                    yield new_num, new_index
            if dict_[curr_num]:
                new_num = curr_num
                for new_index in dict_[curr_num]:
                    if 0 <= new_index < len(arr) and (new_num, new_index) not in visited:
                        yield new_num, new_index
                del dict_[curr_num]

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # corner case
        if len(arr) == 1:
            return 0
        
        # create a better lookup data structure
        dict_ = collections.defaultdict(list)
        for index in range(len(arr)):
            dict_[arr[index]].append(index)
        
        #print(dict_)
            
        # a variable to save ans
        min_count = 0
        
        # remember visited points
        visited = set()
        visited.add((arr[0], 0))
        
        # bfs
        queue = collections.deque()
        queue.append((arr[0], 0))
        
        while queue:
            #print(queue)
            size = len(queue)
            # spread the nodes at the same level
            for i in range(size):
                curr_num, index = queue.popleft()
                #print(\"index: \",index)
                # reach the condition 
                if index == len(arr) - 1:
                    return min_count
                # add unvisited neighbor points to the queue
                for new_num, new_index in self.move(curr_num, index, arr, dict_,visited):
                    if (new_num, new_index) not in visited:
                        #print(\"new_index: \", new_index)
                        visited.add((new_num,new_index))
                        queue.append((new_num, new_index))                                 
            min_count = min_count + 1
        
    
    def move(self, curr_num, index, arr, dict_, visited):
            for new_num, new_index in [(arr[index - 1], index - 1), (arr[index+1], index + 1)]:
                if 0 <= new_index < len(arr) and (new_num, new_index) not in visited:
                    yield new_num, new_index
            if dict_[curr_num]:
                for new_index in dict_[curr_num]:
                    new_num = curr_num
                    if 0 <= new_index < len(arr) and (new_num, new_index) not in visited:
                        yield new_num, new_index
                del dict_[curr_num]

class Solution:
    # bidirectional, best 416 ms, memory 99.90%
    def minJumps(self, arr):
        length = len(arr)
        # if no any connection in nodes, answer equals to array length
        if len(set(arr)) == length: return length - 1
        if arr[0] == arr[-1]: return 1

        _map = defaultdict(set) # connection map
        for i, val in enumerate(arr): _map[val].add(i)

        # BFS, seen: visited index, visit: visited connection
        res, seen, visit = 0, {0}, set()
        # curs: nodes in current side level, other: nodes in opposite side
        curs, other = {0}, {length - 1}
        while curs:
            res += 1
            # store found nodes in this level
            thisLevel = set()
            for i in curs:
                # check move backwards 
                if i - 1 > 0 and i - 1 not in seen: 
                    thisLevel.add(i - 1)
                # check in place
                if arr[i] not in visit: # here can change into \"arr[i] in _map: del _map[arr[i]]\"
                    thisLevel |= (_map[arr[i]] - seen) 
                    visit.add(arr[i])
                # check move forwards
                if i + 1 < length and i + 1 not in seen: 
                    thisLevel.add(i + 1)

            # check if this level and the other side intersect
            if thisLevel & other: return res  

            # update current side for next round          
            curs = thisLevel
            # choose smaller side into next round 
            if len(curs) > len(other): curs, other = other, curs
            # if we don't exchange, put found nodes into seen
            # because they are found in current direction
            else: seen |= thisLevel

#Bidirectional BFS
class Solution:
    def minJumps(self, arr: List[int]) -> int:        
        if len(arr) < 2:
            return 0
        
        graph = {} #存每個值的index
        for i in range(len(arr)):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]
                
        cur = [0] #目前這步要拜訪的index
        visited = {0}
        step = 0
        
        other = [len(arr) - 1] #另一個沒走過的部分
        
        while cur:
            #從較小的開始搜尋
            if len(cur) > len(other):
                cur, other = other, cur
            
            nex = [] #下一步要拜訪的index
            
            for i in cur:
                # check same value
                for node in graph[arr[i]]:
                    if node in other:
                        return step + 1
                    if node not in visited:
                        visited.add(node)
                        nex.append(node)
                graph[arr[i]].clear()  #避免重複拜訪
                
                for x in [i + 1, i - 1]:
                    if x in other:
                        return step + 1
                    if 0 <= x < len(arr) and x not in visited:
                        visited.add(x)
                        nex.append(x)
            cur = nex
            step += 1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        indexMap = collections.defaultdict(list)
        for i,a in enumerate(arr):
            indexMap[a].append(i)
            
        d = deque([(0,0)])
        distance = 0
        visited = {0}
        while d:
            node,distance = d.popleft()
            if node == len(arr)-1:
                return distance
            for nei in [node-1, node+1]+indexMap[arr[node]][::-1]:
                if 0<=nei<len(arr) and nei!=node and nei not in visited:
                    visited.add(nei)
                    if nei == len(arr)-1:
                        return distance+1
                    d.append((nei,distance+1))
        
    
        # def bfs():
        #     from collections import deque
        #     Q = deque([(0,0)])
        #     seen = {0}
        #     while Q:
        #         i, d = Q.popleft()
        #         if i==len(arr)-1:return d
        #         for j in [i-1, i+1]+a_i[arr[i]][::-1]:
        #             if 0<=j<len(arr) and j!=i and j not in seen:
        #                 seen.add(j)
        #                 if j==len(arr)-1:return d+1
        #                 Q.append((j,d+1))
        # return bfs()


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        v2n = collections.defaultdict(set)
        for i, v in enumerate(arr):
            if 0 < i < len(arr) - 1 and arr[i - 1] == v and arr[i + 1] == v:
                continue
            v2n[v].add(i)
        visited, seen, q, step = set([0]), set(), collections.deque([0]), 0
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur == len(arr) - 1: return step
                neighbors = set([cur + 1, cur - 1] + [x for x in v2n[arr[cur]] if arr[cur] not in seen])
                for nb in neighbors:
                    if nb >= 0 and nb < len(arr) and nb != cur and nb not in visited:
                        visited.add(cur)
                        q.append(nb)
                seen.add(cur)
            step += 1
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # corner case
        if len(arr) == 1:
            return 0
        
        # create a better lookup data structure
        dict_ = collections.defaultdict(list)
        for index in range(len(arr)):
            dict_[arr[index]].append(index)
        
        #print(dict_)
            
        # a variable to save ans
        min_count = 0
        
        # remember visited points
        visited = set()
        visited.add((arr[0], 0))
        
        # bfs
        queue = collections.deque()
        queue.append((arr[0], 0))
        
        while queue:
            #print(queue)
            size = len(queue)
            # spread the nodes at the same level
            for i in range(size):
                curr_num, index = queue.popleft()
                #print(\"index: \",index)
                # reach the condition 
                if index == len(arr) - 1:
                    return min_count
                # add unvisited neighbor points to the queue
                for new_num, new_index in self.move(curr_num, index, arr, dict_,visited):
                    if (new_num, new_index) not in visited:
                        #print(\"new_index: \", new_index)
                        visited.add((new_num,new_index))
                        queue.append((new_num, new_index))                                 
            min_count = min_count + 1
        
    
    def move(self, curr_num, index, arr, dict_, visited):
            for new_num, new_index in [(arr[index - 1], index - 1), (arr[index+1], index + 1)]:
                if 0 <= new_index < len(arr):
                    yield new_num, new_index
            if dict_[curr_num]:
                for new_index in dict_[curr_num]:
                    new_num = curr_num
                    if 0 <= new_index < len(arr) and (new_num, new_index) not in visited:
                        yield new_num, new_index
                del dict_[curr_num]

from collections import defaultdict, deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0
        
        graph = defaultdict(list)
        for i, num in enumerate(arr):
            graph[num].append(i)
        
        curr = [0]
        visited = set([0])
        jumps = 0
        
        while curr:
            nxt = []
            
            for node in curr:
                if node == n - 1:
                    return jumps
                
                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nxt.append(child)
                
                graph[arr[node]].clear()
                
                for child in (node-1, node+1):
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nxt.append(child)
                
            curr = nxt
            jumps += 1


from collections import deque,defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        idxs=defaultdict(set)
        for idx,e in enumerate(arr):
            idxs[e].add(idx)
        def bfs(idx):
            q=deque([0])
            step=-1
            not_visited=set(range(len(arr)-1,0,-1))
            while q:
                step+=1
                for _ in range(len(q)):
                    node=q.popleft()
                    if node==len(arr)-1:
                        return step
                    nxt_nodes=idxs[arr[node]]
                    nxt_nodes=not_visited&nxt_nodes
                    for nxt in [node-1,node+1]:
                        if nxt in not_visited:
                            nxt_nodes.add(nxt)
                    if len(arr)-1 in nxt_nodes:
                        return step+1
                    not_visited.difference_update(nxt_nodes)
                    nxt_nodes=nxt_nodes
                    q.extend(nxt_nodes)
            return -1
        return bfs(0)


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr)<=1:
            return 0
        link = collections.defaultdict(list)
        for i, x in enumerate(arr):
            link[x].append(i)
        lvl = 0   
        num_met, pos_met = set(), set()
        # dp = [-1]*len(arr)
        queue = collections.deque([0]) #put index
        while queue:
            L = len(queue)
            for i in range(L):
                x = queue.popleft()
                if x==len(arr)-1: return lvl
                num = arr[x]
                pos_met.add(x)
                
                for k in [x-1, x+1]+ link[num]*(num not in num_met):  #取交集
                    if k in pos_met or not 0<=k<len(arr): continue
                    queue.append(k)
                num_met.add(num)
            lvl +=1
        return 0
                    
        


from collections import defaultdict

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n_arr = len(arr)
        if n_arr <= 1:
            return 0
        
        value_arr_map = defaultdict(list)
        for i, n in enumerate(arr):
            value_arr_map[n].append(i)
        
        head = [0]
        tail = [n_arr-1]
        visited = {0, n_arr-1}
        n_move = 0
        while head or tail:            
            if len(head) > len(tail):
                head, tail = tail, head 
            
            next_head = []
            for current_index in head:
                current_value = arr[current_index]

                candidates = []
                if current_value in value_arr_map:
                    candidates += value_arr_map[current_value]            
                if current_index < n_arr - 1:
                    candidates += [current_index+1]
                if current_index > 0:
                    candidates += [current_index-1]
                for cand in candidates:
                    if cand in tail:
                        return n_move + 1
                    elif cand not in visited:
                        visited.add(cand)
                        next_head.append(cand)

            if current_value in value_arr_map:
                del value_arr_map[current_value]
            head = next_head                
            n_move += 1
        raise ValueError()

class Solution:
    def minJumps(self, arr):
        n = len(arr)
        if n == 1: return 0 
        
        d = defaultdict(list)
        for i,val in enumerate(arr):
            d[val].append(i)
            
        visited = set([0])
        stack = deque([0])
        k, jumps = len(stack), 1
        while stack:
            k -= 1
            i = stack.popleft()
            childs = [j for j in d.pop(arr[i],[])]
            for j in [i-1,i+1]:
                if 0 <= j < n and arr[j] != arr[i] and j not in visited: childs.append(j)
            for j in childs:
                if j == n-1: return jumps
                visited.add(j)
                stack.append(j)
            if not k:
                k = len(stack)
                jumps += 1
        return jumps

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        print((len(arr)))
        adj = collections.defaultdict(list)
        for i,n in enumerate(arr):
            adj[n].append(i)
        
        #for a in adj:
        #    adj[a].sort(reverse=True)
        
        q=collections.deque()
        q.append( (0,0) )  # position, step
        
        used=[False]*len(arr)
        
        i=0
        while q:
            cur,step=q.popleft()
            print((len(q)))
            
            if cur==len(arr)-1:
                return step
            
                   
            if cur<len(arr)-1 and not used[cur+1]:
                used[cur+1]=True
                q.append((cur+1,step+1))
                
            if cur>0 and not used[cur-1]:
                used[cur-1]=True
                q.append((cur-1, step+1))
                
            for nxt in adj[arr[cur]]:
                if (not used[nxt]):
                    used[nxt]=True
                    q.append((nxt,step+1))           
             
            adj[arr[cur]]=[k for k in adj[arr[cur]] if not used[k]]

                
        return -1



class Solution:
    def minJumps1(self, arr: List[int]) -> int:
#         [100,-23,-23,404,100,23,23,23,3,404]
        
#         [0,   1,   2,  2,  1, 2, 3, 3, 4,  3]
        
        if not arr:
            return 0
        
        dp = [float('inf')] * len(arr)
        dp[0] = 0
        minIdx = { arr[0]: (0, 0) }
        for i in range(1, len(arr)):
            x = arr[i]
            stepRight = dp[i-1] + 1
            jumpStep = minIdx[x][1] + 1 if x in minIdx else float('inf')
            
            dp[i] = min(stepRight, jumpStep)
            
            if x in minIdx:
                if dp[i] < minIdx[x][1]:
                    minIdx[x] = (i, dp[i])
            else:
                minIdx[x] = (i, dp[i])
            
            j = i - 1
            while j >= 0 and dp[j] > dp[j + 1] + 1:
                dp[j] = dp[j+1] + 1
                y = arr[j]
                if dp[j] < minIdx[y][1]:
                    minIdx[y] = (j, dp[j])
                j -= 1
        
        return dp[-1]
            
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]

        curs = [0]  # store current layers
        visited = {0}
        step = 0

        # when current layer exists
        while curs:
            nex = []

            # iterate the layer
            for node in curs:
                # check if reached end
                if node == n-1:
                    return step

                # check same value
                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                graph[arr[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1

from collections import deque,defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        idxs=defaultdict(set)
        for idx,e in enumerate(arr):
            idxs[e].add(idx)
        def bfs(idx):
            q=deque([0])
            step=-1
            not_visited=set(range(len(arr)-1,0,-1))
            while q:
                step+=1
                for _ in range(len(q)):
                    node=q.popleft()
                    if node==len(arr)-1:
                        return step
                    nxt_nodes=idxs[arr[node]]
                    del idxs[arr[node]]
                    nxt_nodes=not_visited&nxt_nodes
                    for nxt in [node-1,node+1]:
                        if nxt in not_visited:
                            nxt_nodes.add(nxt)
                    if len(arr)-1 in nxt_nodes:
                        return step+1
                    not_visited.difference_update(nxt_nodes)
                    nxt_nodes=sorted(nxt_nodes,reverse=True)
                    q.extend(nxt_nodes)
            return -1
        return bfs(0)


class Solution:
    def minJumps(self, arr: List[int]) -> int:

        
        # Each array index is a node
        # Each link (i+1), (i-1), (arr[i] == arr[j]) is a connection
        # Create a graph of arr
        # BFS to find the shortest path from 0 to arr.length - 1
        
        if len(arr) == 1: return 0
        
        val_to_id = collections.defaultdict(set)
        id_to_neigh = {}
        
        for i,val in enumerate(arr):
            if (not i) or (i == len(arr) - 1):
                val_to_id[val].add(i)
            elif not (arr[i-1] == arr[i] == arr[i+1]):
                val_to_id[val].add(i)
        
        for i,val in enumerate(arr):
            if (not i) or (i == len(arr) - 1):
                id_to_neigh[i] = set([i-1,i+1])|val_to_id[val]
                id_to_neigh[i] -= set([-1, len(arr), i])
            elif not (arr[i-1] == arr[i] == arr[i+1]):
                id_to_neigh[i] = set([i-1,i+1])|val_to_id[val]
                id_to_neigh[i].remove(i)
                
        t = len(arr) - 1 # target index
        q = [(0, 0)] # (n) number of jumps, (i) current index
        v = set([0])

        while q:
            
            level = []
            
            for n, i in q:
                if i == t:
                    return n
                for j in id_to_neigh.get(i, []):
                    if j not in v:
                        v.add(j)
                        level.append((n+1, j))
            q = level

class Solution:
    def minJumps(self, a: List[int]) -> int:
        n = len(a)
        adj = defaultdict(list)
        for i, x in enumerate(a):
            adj[x].append(i)
        q = [(0, 0)]
        seen = [False] * n
        seen[0] = True
        for u, d in q:
            if u == n - 1:
                return d
            for v in (u - 1, u + 1):
                if 0 <= v < n and not seen[v]:
                    seen[v] = True
                    q.append((v, d + 1))
            x = a[u]
            for v in adj[x]:
                if not seen[v]:
                    seen[v] = True
                    q.append((v, d + 1))
            if adj[x]:
                adj[x] = [] # remove edges

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        A = len(arr)
        m = defaultdict(list)
        for i, n in enumerate(arr):
            m[n].append(i)
        
        visited = set([-1])
        curr = set([0])
        
        for steps in itertools.count():
            visited.update(curr)
            
            if A - 1 in visited:
                return steps
            
            curr = { j for i in curr for j in [i-1, i+1] + m.pop(arr[i], []) if j not in visited }
            
            # curr = { k for j in curr for k in [j+1, j-1] + m.pop(arr[j], []) } - visited
        
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        nei = collections.defaultdict(list)
        for i, x in enumerate(arr):
            nei[x].append(i)

        frontier = collections.deque([(0,0)])
        num_met, pos_met = set(), set()
        while frontier:
            pos, step = frontier.popleft() # state: position, step
            if pos == len(arr) - 1: return step
            num = arr[pos]
            pos_met.add(pos) # track explored positions

            for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
                if p in pos_met or not 0 <= p < len(arr): continue
                frontier.append((p, step + 1))

            num_met.add(num) # track explored values
        
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        to_index = {}
        for i in range(len(arr)):
            if arr[i] not in to_index:
                to_index[arr[i]] = []
            to_index[arr[i]].append(i)
        
        n = len(arr)
        q = [(0,0)]
        vis = set([0])

        for i, jumps in q:
            if i == n-1:
                return jumps
            if i+1<n and i+1 not in vis:
                vis.add(i+1)
                q.append((i+1,jumps+1))
            if i-1>=0 and i-1 not in vis:
                vis.add(i-1)
                q.append((i-1,jumps+1))
            for j in to_index[arr[i]]:
                if j not in vis:
                    q.append((j,jumps+1))
                    vis.add(j)
            to_index[arr[i]] = []
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n<=1:
            return 0
        
        seen = set([0])
        
        dic = collections.defaultdict(set)
        for i,num in enumerate(arr):
            dic[num].add(i)
        
        bfs = collections.deque([[0,0]])
        while bfs:
            ind,c = bfs.popleft()
            if ind==n-1:
                return c
            for nind in [ind-1,ind+1]:
                if 0<=nind<n and nind not in seen:
                    bfs.append([nind,c+1])
                    seen.add(nind)
            for child in dic[arr[ind]]:
                if child not in seen:
                    seen.add(child)
                    bfs.append([child,c+1])
            dic[arr[ind]] = set()


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        index = {}
        if len(set(arr))>10:
            for ic,val in enumerate(arr):
                index[val] = index.get(val,[])+[ic]
        else:
            for val in set(arr):
                index[val] = [ ic for ic,v0 in enumerate(arr) if v0==val]
#        print(len(index),len(arr))
#        return 6
        neigh = {}
        for ic,val in enumerate(arr):
            if ic-1>=0:
                neigh[ic]= neigh.get(ic,[])+[ic-1]
            if ic+1<len(arr):
                neigh[ic]= neigh.get(ic,[])+[ic+1]
        front = [0]; visited = {0:0}
        checkedvalues = set()
        while front!=[]:
            nf = [];
            for u in front:
                val = arr[u];
                for v in neigh.get(u,[]):
                    if not v in visited:
                        visited[v] = visited[u]+1
                        nf.append(v)
                if not val in checkedvalues:
                    for v in index[val]+neigh.get(u,[]):
                        if not v in visited:
                            visited[v] = visited[u]+1
                            nf.append(v)
                checkedvalues.add(val)
            front = nf
        return visited.get(len(arr)-1,-1)

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        L = len(arr)
        if L<2:
            return 0
        cnt = defaultdict(list)
        for i,val in enumerate(arr):
            cnt[val].append(i)
            
        q = deque([0])
        visited = {0}
        steps = 0
        while q:
            size = len(q)
            for _ in range(size):
                n = q.popleft()
                if n==L-1:
                    return steps
                for el in cnt[arr[n]]:
                    if el not in visited:
                        q.append(el)
                        visited.add(el)
                cnt[arr[n]].clear()
                for c in [n-1,n+1]:
                    if 0<=c<L and c not in visited:
                        q.append(c)
                        visited.add(c)
            steps += 1
        
        return steps
                
                


# 1345. Jump Game IV
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        maps = collections.defaultdict(list)
        [maps[a].append(i) for i, a in enumerate(arr)]
 
        begins = set([0])
        ends = set([len(arr) - 1])
        visitedIdx = set([-1, len(arr)])
        for steps in range(len(arr)):
            if len(begins) > len(ends):
                begins, ends = ends, begins
            nextLevels = set()
            for b in begins:
                if b in ends:
                    return steps
                if b in visitedIdx:
                    continue
                visitedIdx.add(b)
                nextLevels.update([b - 1, b + 1] + maps[arr[b]])
                maps.pop(arr[b])
            begins = nextLevels

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        d = defaultdict(list)
        n = len(arr)

        for i in range(n):
            d[arr[i]].append(i)

        vis = [0] * n
        vis[0] = 1
        q = [(0, 0)]
        while q:
            i, k = q.pop(0)
            for j in d[arr[i]] + [i - 1, i + 1]:
                if j < 0 or j >= n or vis[j]:
                    continue
                if j == n - 1:
                    return k + 1
                vis[j] = 1
                q.append((j, k + 1))
            d[arr[i]] = []

        return 0


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # Compress the array:
        # for any sub array s[i] == s[i+1] == s[i+2]... we only care about the start and the end        
        arr = [x for i, x in enumerate(arr) if i == 0 or i == len(arr)-1 or x != arr[i-1] or x != arr[i+1]]
        
        d = {}
        # O(N)
        for i, x in enumerate(arr):
            d.setdefault(x, set()).add(i)
        # Build graph O(N^2)
        adj = {}
        for i, x in enumerate(arr):
            adj[i] = set()
            if i != 0: adj[i].add(i-1)
            if i != len(arr)-1: adj[i].add(i+1)
            adj[i] |= d[arr[i]] # O(N^2)?
            adj[i].remove(i)
            
        #print(adj)
        # BFS
        q = collections.deque()
        distance = [len(arr)-1] * len(arr)
        q.append(0)
        count = 0
        while q:
            nxt_q = collections.deque()
            while q:
                nxt = q.popleft()
                if distance[nxt] <= count: continue
                distance[nxt] = count
                for x in adj[nxt]:
                    nxt_q.append(x)
            q = nxt_q
            count += 1
        return distance[-1]


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        print((len(arr)))
        adj = collections.defaultdict(list)
        for i,n in enumerate(arr):
            adj[n].append(i)
        
        #for a in adj:
        #    adj[a].sort(reverse=True)
        
        q=collections.deque()
        q.append( (0,0) )  # position, step
        
        used=[False]*len(arr)
        
        i=0
        while q:
            cur,step=q.popleft()
            print((len(q)))
            
            if cur==len(arr)-1:
                return step
            
                   
            if cur<len(arr)-1 and not used[cur+1]:
                used[cur+1]=True
                q.append((cur+1,step+1))
                
            if cur>0 and not used[cur-1]:
                used[cur-1]=True
                q.append((cur-1, step+1))
                
            for nxt in adj[arr[cur]]:
                if (not used[nxt]):
                    used[nxt]=True
                    q.append((nxt,step+1))           
             
            adj[arr[cur]]=[k for k in adj[arr[cur]] if not used[nxt]]

                
        return -1



class Solution:
    def minJumps(self, arr):
        nei = collections.defaultdict(list)
        _ = [nei[x].append(i) for i, x in enumerate(arr)]

        frontier = collections.deque([(0,0)])
        num_met, pos_met = set(), set()
        while frontier:
            pos, step = frontier.popleft() # state: position, step
            if pos == len(arr) - 1: return step
            num = arr[pos]
            pos_met.add(pos) # track explored positions

            
            nexts = [pos - 1, pos + 1]+nei[num] if num not in num_met else [pos - 1, pos + 1]
            
            for p in nexts:
                if p in pos_met or not 0 <= p < len(arr): continue
                frontier.append((p, step + 1))

            num_met.add(num) # track explored values
                


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # BFS
        A = arr
        n = len(A)
        q = []
        val_dic = collections.defaultdict(list)
        for i, val in enumerate(A):
            if len(val_dic[val]) > 0:
                last_range = val_dic[val][-1]
                if last_range[1]+1 == i:
                    last_range[1] = i
                else:
                    val_dic[val].append([i,i])
            else:
                val_dic[val].append([i,i])
                
        walked_val = set()
        # for i in val_dic[A[0]]:
        q.append(0)
            
        walked = set()
        steps = -1
        while len(q) > 0:
            # print(q)
            cur_len = len(q)
            next_q = []
            for i in q:
                val = A[i]
                if i == n-1:
                    return steps+1
                
                walked.add(i)
                
                if i+1 < n and i+1 not in walked:
                    next_q.append(i+1)
                if i-1 > -1 and i-1 not in walked:
                    next_q.append(i-1)
                if val not in walked_val:
                    index_range_list = val_dic[val]
                    for index_range in index_range_list:
                        for j in (index_range[0], index_range[1]):
                            if j != i and j not in walked:
                                next_q.append(j)
                        walked_val.add(val)
                
            steps += 1
            q = next_q
        return steps



# class Solution:
#     def minJumps(self, arr: List[int]) -> int:
#         # BFS
#         A = arr
#         n = len(A)
#         q = collections.deque()
#         val_dic = collections.defaultdict(list)
#         for i, val in enumerate(A):
#             if len(val_dic[val]) > 0:
#                 last_range = val_dic[val][-1]
#                 if last_range[1]+1 == i:
#                     last_range[1] = i
#                 else:
#                     val_dic[val].append([i,i])
#             else:
#                 val_dic[val].append([i,i])
                
#         walked_val = set()
#         # for i in val_dic[A[0]]:
#         q.append(0)
            
#         walked = set()
#         steps = -1
#         while len(q) > 0:
#             # print(q)
#             cur_len = len(q)
#             for _ in range(0,cur_len):
                
#                 i = q.popleft()
#                 val = A[i]
#                 if i == n-1:
#                     return steps+1
                
#                 walked.add(i)
                
#                 if i+1 < n and i+1 not in walked:
#                     q.append(i+1)
#                 if i-1 > -1 and i-1 not in walked:
#                     q.append(i-1)

#                 # 不要去遍历和自己的值相同的元素，如果不便利，就增加不进去。
#                 # 如果这个值已经被遍历过了，就不要再次遍历。
                
#                 if val not in walked_val:
#                     index_range_list = val_dic[val]
#                     for index_range in index_range_list:
#                         for j in (index_range[0], index_range[1]):
#                             if j != i and j not in walked:
#                                 q.append(j)
#                         walked_val.add(val)
                
#             steps += 1
                
#         return steps


from collections import defaultdict, deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0
        
        graph = defaultdict(list)
        for i, num in enumerate(arr):
            graph[num].append(i)
        
        curr = [0]
        visited = set([0])
        jumps = 0
        
        while curr:
            nxt = []
            
            for node in curr:
                if node == n - 1:
                    return jumps
                
                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nxt.append(child)
                
                graph[arr[node]].clear()
                
                for child in (node-1, node+1):
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nxt.append(child)
                
            curr = nxt
            jumps += 1
                
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        N = len(arr)
        indices = collections.defaultdict(set)

        for i, a in enumerate(arr):
            indices[a].add(i)

        queue = collections.deque([(0, 0)])        
        seen = {0}
        value_seen = set()

        while queue:
            i, move = queue.popleft()

            if i == N-1:
                return move

            if arr[i] not in value_seen:
                value_seen.add(arr[i])
                for j in indices[arr[i]]:
                    if j != i and j not in seen:
                        seen.add(j)
                        queue.append((j, move+1))

            if i-1 >= 0 and (i-1) not in seen:
                seen.add(i-1)
                queue.append((i-1, move+1))
            
            if i+1 < N and (i+1) not in seen:
                seen.add(i+1)
                queue.append((i+1, move+1))

import numpy as np
import heapq
from collections import deque

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        self.arr = arr

        # Hashing indices by values
        self.val2indx = {}
        for i,v in enumerate(arr):
            if not v in self.val2indx:  self.val2indx[v] = []
            self.val2indx[v].append(i)
        # print(\"val hash: \", self.val2indx)

        # Solutions memoization table
        self.solutions = [np.inf for i in range(len(arr))]
        self.solutions[-1] = 0
        self.visited = [False for i in range(len(arr))]
        
        node_q = deque()
        node_q.append((0, len(arr)-1))
        
        while node_q:
            # dist, indx = heapq.heappop(node_q)
            dist, indx = node_q.popleft()
            self.visited[indx] = True
            if dist > self.solutions[indx]: continue
                
            # Extracting edges
            next_indx, prev_indx = min(indx+1, len(self.arr)-1), max(indx-1, 0)
            indices = [i for i in self.val2indx[self.arr[indx]] if i != indx and i != prev_indx and i != next_indx and not self.visited[i]]    
            indices = [prev_indx, next_indx] + indices
            if not self.visited[prev_indx]: indices.append(prev_indx)
            if not self.visited[next_indx]: indices.append(next_indx)
            # exclude already visited nodes
            # indices = [i for i in indices if not self.visited[i]]
            # print(\"node:\", indx, \"edges\", indices)
                            
            # Update neighbour distances
            for j in indices:
                newdist = dist + 1
                if np.isinf(self.solutions[j]) or newdist < self.solutions[j] and not self.visited[j]:
                    self.solutions[j] = newdist
                    # heapq.heappush(node_q, (newdist, j))
                    node_q.append((newdist,j))
                    self.visited[j] = True
                    if j == 0: return newdist
        
        # print(\"solutions:\", self.solutions)
        return self.solutions[0]
            
            
        
        


# class Solution:
#     def getSolution(self, indx):
#         self.visitations[indx] = True
        
#         # Checking presence in hash table for the solution
#         if self.solutions[indx] is not None:
#             return self.solutions[indx]
#         else:
#             # min(indx-1, indx+1, indicees of val2indx[arr[indx]])
#             indices = [i for i in self.val2indx[self.arr[indx]] if i != indx]
#             indices = [min(indx+1, len(self.arr)-1), max(indx-1, 0)] + indices
#             indices = np.unique(indices)         
#             # exclude already visited states
#             indices = [i for i in indices if not self.visitations[i] or self.solutions[i] is not None]
#             print(indx, indices, self.solutions)
            
#             solutions = []
#             for i in indices:
#                 solutions.append(self.getSolution(i))
                
#                 # Just a shortcut to avoid unnecessary search
#                 if solutions[-1] == 1: 
#                     self.solutions[indx] = 2
#                     return self.solutions[indx]
            
#             if len(solutions) == 0: return np.inf
            
#             print(\"---\", indx ,\":\", solutions, np.min(solutions), indices)
#             self.solutions[indx] = 1 + np.min(solutions)
#             return self.solutions[indx]
    
#     def minJumps(self, arr: List[int]) -> int:
#         self.arr = arr

#         # Solutions memoization table
#         self.solutions = [None for i in range(len(arr))]
#         self.solutions[-1] = 0
#         self.solutions[-2] = 1
#         # self.visitations = [False for i in range(len(arr))]
#         # self.visitations[-2] = True
        
#         # Hashing indices by values
#         self.val2indx = {}
#         for i,v in enumerate(arr):
#             if not v in self.val2indx:  self.val2indx[v] = []
#             self.val2indx[v].append(i)
        
#         print(\"arr:\", arr)
#         print(\"val hash:\", self.val2indx)
#         # return 0
        
#         # Get solutions starting from the end
#         for i in range(len(arr)-2, -1, -1):
#             print(\"indx:\", i)
#             self.visitations = [False for j in range(len(arr))]
#             self.visitations[-2] = True
#             self.getSolution(indx=i)
        
        
#         print(\"solutions: \", self.solutions)
#         return self.solutions[0]
        
        


class Solution:
    # bidirectional, best 416 ms, memory 99.90%
    def minJumps(self, arr):
        length = len(arr)
        # if no any connection in nodes, answer equals to array length
        if len(set(arr)) == length: return length - 1
        if arr[0] == arr[-1]: return 1

        _map = defaultdict(set) # connection map
        for i, val in enumerate(arr): _map[val].add(i)

        # BFS, seen: visited index, visit: visited connection
        res, seen, visit = 0, {0}, set()
        # curs: nodes in current side level, other: nodes in opposite side
        curs, other = {0}, {length - 1}
        while curs:
            res += 1
            # store found nodes in this level
            thisLevel = set()
            for i in curs:
              
                # check move backwards 
                if i - 1 > 0 and i - 1 not in seen: 
                    thisLevel.add(i - 1)
                # check in place
                if arr[i] not in visit:
                    thisLevel |= (_map[arr[i]] - seen) 
                    visit.add(arr[i])
                # check move forwards
                if i + 1 < length and i + 1 not in seen: 
                    thisLevel.add(i + 1)

            # check if this level and the other side intersect
            if thisLevel & other: return res  

            # update current side for next round          
            curs = thisLevel
            # choose smaller side into next round 
            if len(curs) > len(other): curs, other = other, curs
            # if we don't exchange, put found nodes into seen
            # because they are found in current direction
            else: seen |= thisLevel

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr or len(arr)==1:
            return 0
        
        dp=[float('inf')]*len(arr)
        dp[0]=0
        
        position=collections.defaultdict(set)
        visited={}
        for i,e in enumerate(arr):
            position[e].add(i)
            visited[i]=False
        visited[0]=True
        
        start={0}
        step=0
        while start:
            nextstart=set()
            for i in start:
                
                if i==len(arr)-1:
                    return step
                
                if i-1>=0 and not visited[i-1]:
                    dp[i-1]=min(dp[i-1],dp[i]+1)
                    nextstart.add(i-1)
                    visited[i-1]=True
                if i+1<len(arr) and not visited[i+1]:
                    dp[i+1]=min(dp[i+1],dp[i]+1)
                    nextstart.add(i+1)
                    visited[i+1]=True
                for p in position[arr[i]]:
                    if p!=i and not visited[p]:
                        dp[p]=min(dp[p],dp[i]+1)
                        nextstart.add(p)
                        visited[p]=True
                position[arr[i]]=set()

            start=nextstart
            step+=1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        s = defaultdict(list)
        for i,num in enumerate(arr):
            s[num] += [i]
            
        q = set([0])
        seen = set()
        level = 0
        while q:
            seen.update(q)
            new_q = set()
            for i in q:
                if i == len(arr)-1:
                    return level
                children = []
                if i+1 < len(arr):
                    children += [i+1]
                if i-1 >= 0:
                    children += [i-1]
                for j in s[arr[i]]:
                    if j != i:
                        children += [j]
                del s[arr[i]]
                        
                for child in children:
                    if child not in seen:
                        new_q.add(child)
            level += 1
            q = new_q


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        d = {}
        seen = set()
        queue = deque([(0, 0)])
        
        for i, num in enumerate(arr):
            if i == 0 or i == len(arr)-1 or (arr[i-1] != arr[i] or arr[i+1] != arr[i]):
                d[num] = d.get(num, []) + [i]
        
        while queue:
            next_idx, steps = queue.popleft()
            
            if next_idx == len(arr)-1:
                return steps
            
            if next_idx + 1 <= len(arr) and next_idx + 1 not in seen:
                queue.append((next_idx+1, steps+1))
                seen.add(next_idx+1)
            
            if next_idx - 1 >= 0 and next_idx - 1 not in seen:
                queue.append((next_idx-1, steps+1))
                seen.add(next_idx-1)
            
            for i in d[arr[next_idx]][::-1]:
                if i != next_idx and i not in seen:
                    queue.append((i, steps+1))
                    seen.add(i)
        
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # U could do this in BFS

        
        record = collections.defaultdict(list)
        for i,v in enumerate(arr):
            record[v].append(i)
        nums = set()
        pos_met = set()
        q = collections.deque([(0,0)])
        while q:
            pos,step = q.popleft()
            if pos == len(arr)-1:return step
            num = arr[pos]
            pos_met.add(pos)
            temp = [pos-1,pos+1]
            if num not in nums:
                for j in record[num]:
                    temp += [j]
            nums.add(num)
            for i in temp:
                if 0<=i<len(arr) and i not in pos_met:
                    q.append([i,step+1])


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        def BFS(queue):
            seen = [1]*len(arr);seen[0] = 0
            while queue:
                var , level = queue.pop(0)
                if var == len(arr) - 1:return level
                if seen[var + 1]:queue.append([var+1,level+1]);seen[var+1] = 0
                if var - 1 >=0 and   seen[var - 1]:queue.append([var-1,level+1]);seen[var-1] = 0                 
                for i in d[arr[var]]:
                    if seen[i]:queue.append([i,level+1]);seen[i] = 0
                d[arr[var]].clear()
        
        d = defaultdict(list)
        for i in range(len(arr) - 1 , -1 ,-1 ):d[arr[i]] +=[i]
        return (BFS([[0,0]]))

from collections import defaultdict, deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr)==1: return 0
        
        VALUE_INDEX_MAP = defaultdict(list)
        for i, v in enumerate(arr):
            VALUE_INDEX_MAP[v].append(i)
        
        # BFS
        queue = deque([0])
        seen = set([0])
        nsteps = -1
        while queue:
            levelSize = len(queue)
            nsteps += 1
            for _ in range(levelSize):
                x = queue.popleft()
                if x == len(arr)-1:
                    return nsteps
                for nx in VALUE_INDEX_MAP[arr[x]]+[x-1, x+1]:
                    if 0<=nx<len(arr) and nx not in seen:
                        queue.append(nx)
                        seen.add(nx)
                VALUE_INDEX_MAP[arr[x]].clear() # this ensures that the same value can be visited at most twice.
                
        return -1

from collections import deque
from collections import defaultdict

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        mapping = defaultdict(set)
        for i, val in enumerate(arr):
            mapping[val].add(i)

        queue = deque([(0, 0)])
        visited = set([0])
        while queue:
            curr_cost, ci = queue.popleft()
            if ci == len(arr) - 1:
                return curr_cost
            if ci + 1 < len(arr) and ci + 1 not in visited:
                queue.append((curr_cost + 1, ci + 1))
                visited.add(ci + 1)
                if ci + 1 in mapping[arr[ci]]:
                    mapping[arr[ci]].remove(ci + 1)
            if ci - 1 >= 0 and ci - 1 not in visited:
                queue.append((curr_cost + 1, ci - 1))
                visited.add(ci - 1)
                if ci - 1 in mapping[arr[ci]]:
                    mapping[arr[ci]].remove(ci - 1)
            next_ = set(mapping[arr[ci]])
            for ni in next_:
                if ni not in visited:
                    queue.append((curr_cost + 1, ni))
                    visited.add(ni)
                mapping[arr[ci]].remove(ni)
        return -1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        def BFS(queue):
            seen , val_seen = [1]*len(arr) , set();seen[0] = 0
            while queue:
                var , level = queue.pop(0)
                if var == len(arr) - 1:return level
                if seen[var + 1]:queue.append([var+1,level+1]);seen[var+1] = 0
                if var - 1 >=0 and   seen[var - 1]:queue.append([var-1,level+1]);seen[var-1] = 0
                if arr[var] not in val_seen:  
                    for i in d[arr[var]]:
                        if seen[i]:queue.append([i,level+1]);seen[i] = 0
                    val_seen.add(arr[var])
        
        d = defaultdict(list)
        for i in range(len(arr) - 1 , -1 ,-1 ):d[arr[i]] +=[i]
        return (BFS([[0,0]]))

# class Solution:
#     def minJumps(self, arr: List[int]) -> int:
#         n = len(arr)
#         if n <= 1:
#             return 0

#         graph = {}
#         for i in range(n):
#             if arr[i] in graph:
#                 graph[arr[i]].append(i)
#             else:
#                 graph[arr[i]] = [i]

#         curs = [0]  # store current layers
#         visited = {0}
#         step = 0

#         # when current layer exists
#         while curs:
#             nex = []

#             # iterate the layer
#             for node in curs:
#                 # check if reached end
#                 if node == n-1:
#                     return step

#                 # check same value
#                 for child in graph[arr[node]]:
#                     if child not in visited:
#                         visited.add(child)
#                         nex.append(child)

#                 # clear the list to prevent redundant search
#                 graph[arr[node]].clear()

#                 # check neighbors
#                 for child in [node-1, node+1]:
#                     if 0 <= child < len(arr) and child not in visited:
#                         visited.add(child)
#                         nex.append(child)

#             curs = nex
#             step += 1

#         return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr or len(arr) == 1: return 0
        
        val_to_idxes = collections.defaultdict(list)
        adj = collections.defaultdict(set)
        
        for i in range(len(arr)):
            val_to_idxes[arr[i]].append(i)
        
        # bfs
        # [(idx, dist)]
        q = [(0, 0)]
        visited = {0}
        while q:
            idx, dist = q.pop(0)
        
            if idx == len(arr) - 1:
                return dist
            
            visited.add(idx)

            for neighbor in val_to_idxes[arr[idx]]:

                if neighbor in visited:
                    continue

                q.append((neighbor, dist+1))
                visited.add(neighbor)
                
                if neighbor == len(arr) - 1:
                    return dist+1            
            
            if idx-1 >= 0 and (idx-1) not in visited:
                q.append((idx-1, dist+1))
                visited.add(idx-1)

            if idx+1 < len(arr) and (idx+1) not in visited:
                q.append((idx+1, dist+1))
                visited.add(idx+1)
                
                if idx+1 == len(arr)-1:
                    return dist + 1


            
            val_to_idxes[arr[idx]] = []
        
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        dic = defaultdict(list)
        for i in range(len(arr)):
            dic[arr[i]].append(i)
        visited = [False] * (len(arr))
        queue=collections.deque()
        queue.append((0,0))
        ans = 0
        N = len(arr)
        while(queue):
            i,step = queue.popleft()
            print((i,step))
            if(i == N-1):
                ans = step
                break
            if visited[i] == False:
                if(i+1<N):
                    queue.append((i+1,step+1))
                if(i-1>=0):
                    queue.append((i-1,step+1))
                for index in dic[arr[i]]:
                    if(visited[index] == False):
                        queue.append((index,step+1))
                visited[i] = True
                dic[arr[i]] = []  
                        
        return ans


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 2:
            return 0
        
        graph = defaultdict(list)
        for i, v in enumerate(arr):
            graph[v].append(i)
        
        queue = [0]
        seen = {0}
        steps = 0
        while queue:
            next_ = []
            for node in queue:
                if node == n - 1:
                    return steps
                for neighbor in graph[arr[node]]:
                     
                    if neighbor not in seen:
                        seen.add(neighbor)
                        next_.append(neighbor)
                
                for neighbor in [node-1, node+1]:
    
                    if 0 <= neighbor < n and neighbor not in seen:
                        seen.add(neighbor)
                        next_.append(neighbor)
                graph[arr[node]].clear()        
                        
            queue = next_
            steps += 1
            
        return -1

# class Solution:
#     def minJumps(self, arr: List[int]) -> int:
#         n = len(arr)
#         if n <= 1:
#             return 0

#         graph = {}
#         for i in range(n):
#             if arr[i] in graph:
#                 graph[arr[i]].append(i)
#             else:
#                 graph[arr[i]] = [i]

#         curs = [0]  # store current layers
#         visited = {0}
#         step = 0

#         # when current layer exists
#         while curs:
#             nex = []

#             # iterate the layer
#             for node in curs:
#                 # check if reached end
#                 if node == n-1:
#                     return step

#                 # check same value
#                 for child in graph[arr[node]]:
#                     if child not in visited:
#                         visited.add(child)
#                         nex.append(child)

#                 # clear the list to prevent redundant search
#                 graph[arr[node]].clear()

#                 # check neighbors
#                 for child in [node-1, node+1]:
#                     if 0 <= child < len(arr) and child not in visited:
#                         visited.add(child)
#                         nex.append(child)

#             curs = nex
#             step += 1

#         return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr or len(arr) == 1: return 0
        
        val_to_idxes = collections.defaultdict(list)
        adj = collections.defaultdict(set)
        
        for i in range(len(arr)):
            val_to_idxes[arr[i]].append(i)
        
        # bfs
        # [(idx, dist)]
        q = [(0, 0)]
        visited = {0}
        while q:
            idx, dist = q.pop(0)
        
            if idx == len(arr) - 1:
                return dist
            
            visited.add(idx)

            for neighbor in val_to_idxes[arr[idx]]:

                if neighbor in visited:
                    continue

                q.append((neighbor, dist+1))
                visited.add(neighbor)
                
                if neighbor == len(arr) - 1:
                    return dist+1            
            
            if idx-1 >= 0 and (idx-1) not in visited:
                q.append((idx-1, dist+1))
                visited.add(idx-1)

            if idx+1 < len(arr) and (idx+1) not in visited:
                q.append((idx+1, dist+1))
                visited.add(idx+1)
                
                if idx+1 == len(arr)-1:
                    return dist + 1
            
            val_to_idxes[arr[idx]] = []
        
        return -1

# class Solution:
#     def minJumps(self, arr: List[int]) -> int:
#         n = len(arr)
#         if n <= 1:
#             return 0

#         graph = {}
#         for i in range(n):
#             if arr[i] in graph:
#                 graph[arr[i]].append(i)
#             else:
#                 graph[arr[i]] = [i]

#         curs = [0]  # store current layers
#         visited = {0}
#         step = 0

#         # when current layer exists
#         while curs:
#             nex = []

#             # iterate the layer
#             for node in curs:
#                 # check if reached end
#                 if node == n-1:
#                     return step

#                 # check same value
#                 for child in graph[arr[node]]:
#                     if child not in visited:
#                         visited.add(child)
#                         nex.append(child)

#                 # clear the list to prevent redundant search
#                 graph[arr[node]].clear()

#                 # check neighbors
#                 for child in [node-1, node+1]:
#                     if 0 <= child < len(arr) and child not in visited:
#                         visited.add(child)
#                         nex.append(child)

#             curs = nex
#             step += 1

#         return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr or len(arr) == 1: return 0
        
        val_to_idxes = collections.defaultdict(list)
        adj = collections.defaultdict(set)
        
        for i in range(len(arr)):
            val_to_idxes[arr[i]].append(i)
        
        # bfs
        # [(idx, dist)]
        q = [(0, 0)]
        visited = {0}
        while q:
            idx, dist = q.pop(0)
        
            if idx == len(arr) - 1:
                return dist
            
            visited.add(idx)
        
            if idx-1 >= 0 and (idx-1) not in visited:
                q.append((idx-1, dist+1))
                visited.add(idx-1)

            if idx+1 < len(arr) and (idx+1) not in visited:
                q.append((idx+1, dist+1))
                visited.add(idx+1)
                
                if idx+1 == len(arr)-1:
                    return dist + 1

            for neighbor in val_to_idxes[arr[idx]]:

                if neighbor in visited:
                    continue

                q.append((neighbor, dist+1))
                visited.add(neighbor)
                
                if neighbor == len(arr) - 1:
                    return dist+1
            
            val_to_idxes[arr[idx]] = []
        
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        def BFS(queue):
            seen , val_seen = [1]*len(arr) , set();seen[0] = 0
            while queue:
                var , level = queue.pop(0)
                if var == len(arr) - 1:return level
                if seen[var + 1]:queue.append([var+1,level+1]);seen[var+1] = 0
                if var - 1 >=0 and   seen[var - 1]:queue.append([var-1,level+1]);seen[var-1] = 0
                if arr[var] not in val_seen:  
                    for i in d[arr[var]]:
                        if seen[i]:queue.append([i,level+1]);seen[i] = 0
                val_seen.add(arr[var])
        
        d = defaultdict(list)
        for i in range(len(arr) - 1 , -1 ,-1 ):d[arr[i]] +=[i]
        return (BFS([[0,0]]))

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        def BFS(queue):
            seen = [1]*len(arr);seen[0] = 0
            while queue:
                var , level = queue.pop(0)
                if var == len(arr) - 1:return level
                if seen[var + 1]:queue.append([var+1,level+1]);seen[var+1] = 0
                if seen[var - 1] and var - 1 >=0 :queue.append([var-1,level+1]);seen[var-1] = 0
                for i in d[arr[var]]:
                    if seen[i]:queue.append([i,level+1]);seen[i] = 0
                d[arr[var]].clear()
        
        d = defaultdict(list)
        for i in range(len(arr) - 1 , -1 ,-1 ):d[arr[i]] +=[i]
        return (BFS([[0,0]]))

import collections
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0
        
        d = collections.defaultdict(list)
        for index, element in enumerate(arr):
            d[element].append(index)

        queue = collections.deque([(0, 0)])
        s = set()
        s.add(0)

        while len(queue):
            currIndex, jumps = queue.popleft()

            for nextIndex in [currIndex + 1, currIndex - 1] + d[arr[currIndex]][::-1]:
                if nextIndex < len(arr) and nextIndex > -1 and nextIndex != currIndex and nextIndex not in s:
                    if nextIndex == len(arr) - 1:
                        return jumps + 1
                    s.add(nextIndex)
                    queue.append((nextIndex, jumps + 1))

        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        print((len(arr)))
        adj = collections.defaultdict(list)
        for i,n in enumerate(arr):
            adj[n].append(i)
        
        #for a in adj:
        #    adj[a].sort(reverse=True)
        
        q=collections.deque()
        q.append( (0,0) )  # position, step
        
        used=[False]*len(arr)
        
        i=0
        while q:
            cur,step=q.popleft()
            print((len(q)))
            
            if cur==len(arr)-1:
                return step
            
                   
            if cur<len(arr)-1 and not used[cur+1]:
                used[cur+1]=True
                q.append((cur+1,step+1))
                
            if cur>0 and not used[cur-1]:
                used[cur-1]=True
                q.append((cur-1, step+1))
                
            for nxt in adj[arr[cur]]:
                if (not used[nxt]):
                    used[nxt]=True
                    q.append((nxt,step+1))           
            
            adj[arr[cur]]=[]
             

                
        return -1




class Solution:
    def minJumps(self, arr: List[int]) -> int:
        #minJump, shortest Path
        
        minJump = len(arr) + 1
        graph = {}
        for i, n in enumerate(arr):
            if 1 < i <len(arr)-1 and arr[i-1] == arr[i] == arr[i+1]: ###pruning, skip the middle of the contiguous number
                continue
            graph[n] = graph.get(n, [])
            graph[n].append(i)
        
        queue = collections.deque([0])
        visited = set([0])
        step = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                if node == len(arr) - 1:
                    return step
                num = graph.pop(arr[node], [])  ##arr[node], not node
                for nei in [node + 1, node - 1] +num:
                    if nei not in visited and  0 <= nei < len(arr):
                        queue.append(nei)
                        visited.add(nei)
            step += 1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n==1:
            return 0
        if arr[-1] == arr[0]:
            return 1
        mapping = collections.defaultdict(list)
        for i, num in enumerate(arr):
            mapping[num].append(i)
        q = collections.deque([(0, 0)])
        visited = set([0])
        while q:
            cur_i, jumps = q.popleft()
            if cur_i == n-1:
                return jumps
            curnum = arr[cur_i]
            for nei_i in mapping[curnum]:
                if nei_i != cur_i and nei_i not in visited:
                    visited.add(nei_i)
                    q.append((nei_i, jumps+1))
            # clear the neighbors, since we have tried every 
            # jumping ways in this mapping and we do not to
            # jump back
            mapping[curnum] = []
            if cur_i+1 < n and cur_i+1 not in visited:
                visited.add(cur_i+1)
                q.append((cur_i+1, jumps+1))
            if cur_i-1>=0 and cur_i-1 not in visited:
                visited.add(cur_i-1)
                q.append((cur_i-1, jumps+1))
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        c = collections.defaultdict(list)
        for i, x in enumerate(arr):
            c[x].append(i)
        
        q = [0]
        steps = [0] * len(arr)
        steps[0] = 1
        seen = set()
        
        while q:
            i = q.pop(0)
            if i == len(arr) -1: return steps[i]-1
            children = [i-1, i+1]
            if arr[i] not in seen:
                children += c[arr[i]][::-1]
                seen.add(arr[i])
            for child in children:
                if child < 0 or child >= len(arr): continue
                if child == i: continue
                if steps[child]: continue
                steps[child] = steps[i] + 1
                q.append(child)
        
        return steps[-1] - 1


from collections import defaultdict, deque

import heapq

class Solution:
  def minJumps(self, arr: List[int]) -> int:
    n = len(arr)
    # priority queue, O(NlogN)
    d = defaultdict(set)
    for i, x in enumerate(arr):
      d[x].add(i)
    q, s = [(0, 0)], defaultdict(lambda: float('inf'))
    s[0] = 0
    while q:
      m, i = heapq.heappop(q)
      i = -i
      if i - 1 >= 0 and s[i - 1] > m + 1:
        s[i - 1] = m + 1
        heapq.heappush(q, (m + 1, -(i - 1)))
      if i + 1 < n and s[i + 1] > m + 1:
        if i + 1 == n - 1:
          return m + 1
        s[i + 1] = m + 1
        heapq.heappush(q, (m + 1, -(i + 1)))
      x, js = arr[i], set()
      for j in d[x]:
        if s[j] > m + 1:
          if j == n - 1:
            return m + 1
          s[j] = m + 1
          heapq.heappush(q, (m + 1, -j))
        else:
          js.add(j)
      for j in js:
        d[x].remove(j)
    return s[n - 1]

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        graph = defaultdict(list)
        for i, num in enumerate(arr):
            graph[num].append(i)
        q = deque([0])
        counter = 0
        visited = [0] * len(arr)
        visited[0] = 1
        while q:
            size = len(q)
            for _ in range(size):
                i = q.popleft()
                if i == len(arr) - 1:
                    return counter
                num = arr[i]
                neighbors = graph[num]
                for neighbor in neighbors:
                    if not visited[neighbor]:
                        q.append(neighbor)
                        visited[neighbor] = 1
                graph.pop(num)
                if i + 1 < len(arr) and not visited[i + 1]:
                    q.append(i + 1)
                    visited[i + 1] = 1
                if i - 1 >= 0 and not visited[i - 1]:
                    q.append(i - 1)
                    visited[i - 1] = 1
            counter += 1



class Solution:
    def minJumps(self, arr: List[int]) -> int:
        dic = defaultdict(list)
        for i in range(len(arr)):
            dic[arr[i]].append(i)
        visited = [False] * (len(arr))
        queue=collections.deque()
        queue.append((0,0))
        ans = 0
        N = len(arr)
        while(queue):
            i,step = queue.popleft()
            print((i,step))
            if(i == N-1):
                ans = step
                break
            if visited[i] == False:
                if(i+1<N and not visited[i+1]):
                    queue.append((i+1,step+1))
                if(i-1>=0 and not visited[i-1]):
                    queue.append((i-1,step+1))
                for index in dic[arr[i]]:
                    if(visited[index] == False):
                        queue.append((index,step+1))
                visited[i] = True
                dic[arr[i]] = []  
                        
        return ans


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        endpos = len(arr)-1
        graph = {}
        for i,n in enumerate(arr):
            if n not in graph:
                graph[n] = []
            graph[n].append(i)
        
        curr = set([0])
        hit = set()
        mark = 0
        while curr:
            nxt = set()
            for i in curr:
                hit.add(i)
                if i == endpos:
                    return mark
                if i != 0 and i-1 not in hit:
                    nxt.add(i-1)
                if i+1 not in hit:
                    nxt.add(i+1)
                if arr[i] in graph:
                    nxt.update([j for j in graph[arr[i]] if i != j and j not in hit])
                    del graph[arr[i]]
            mark += 1
            curr = nxt
        return -1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        #minJump, shortest Path
        
        minJump = len(arr) + 1
        graph = {}
        for i, n in enumerate(arr):
            if 1 < i <len(arr)-1 and arr[i-1] == arr[i] == arr[i+1]:
                continue
            graph[n] = graph.get(n, [])
            graph[n].append(i)
        
        queue = collections.deque([0])
        visited = set([0])
        step = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                if node == len(arr) - 1:
                    return step
                num = graph.pop(arr[node], [])
                for nei in [node + 1, node - 1] +num:
                    if nei not in visited and  0 <= nei < len(arr):
                        queue.append(nei)
                        visited.add(nei)
            step += 1

        
        
        

#         num2Index = {}
#         for i, item in enumerate(arr):
#             if i> 1 and i < len(arr)-1 and arr[i] == arr[i+1] == arr[i-1] : 
#                 continue
#             if item in num2Index:
#                 num2Index[item].append(i)
#             else:
#                 num2Index[item] = [i]
            

#         queue = [(0, 0)] 
#         visited = set({0})
#         step = 0

#         while queue:
#             size =len(queue)
#             for _ in range(size):
#                 pos, step = queue.pop(0)
#                 if pos == len(arr) -1 :
#                     return step
#                 num = num2Index.pop(arr[pos], [])
#                 for newpos in [pos + 1, pos - 1] + num:
#                     if 0 <= newpos < len(arr) and newpos != pos and newpos not in visited:
#                         visited.add(newpos)
#                         if newpos == len(arr) -1 :
#                             return step+1
#                         queue.append((newpos, step + 1))
                
#         return step


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # U could do this in BFS, dont over thinking!
        # Start from 0,0 (position, step)
        # Record all the numbers and positions stepped on
        # Once u stepped on certain number, u will try out all the candidates
        # So no twice on the same number
        # And each time check within valid range
        record = collections.defaultdict(list)
        for i,v in enumerate(arr):
            record[v].append(i)
        nums = set()
        pos_met = set()
        q = collections.deque([(0,0)])
        while q:
            pos,step = q.popleft()
            if pos == len(arr)-1:return step
            num = arr[pos]
            pos_met.add(pos)
            temp = [pos-1,pos+1]
            if num not in nums:
                for j in record[num]:
                    temp += [j]
            nums.add(num)
            for i in temp:
                # Here, even though u make sure the num is not stepped on 
                # Remember to check if the position is stepped on!
                if 0<=i<len(arr) and i not in pos_met:
                    q.append([i,step+1])


class Solution:
    def minJumps(self, arr) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]

        curs = [0]  # store layers from start
        visited = {0, n-1}
        step = 0

        other = [n-1] # store layers from end

        # when current layer exists
        while curs:
            # search from the side with fewer nodes
            if len(curs) > len(other):
                curs, other = other, curs
            nex = []

            # iterate the layer
            for node in curs:

                # check same value
                for child in graph[arr[node]]:
                    if child in other:
                        return step + 1
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                graph[arr[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if child in other:
                        return step + 1
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        graph = defaultdict(set)
        for i, num in enumerate(arr):
            graph[num].add(i)
        q = deque([0])
        counter = 0
        visited = [0] * len(arr)
        visited[0] = 1
        while q:
            size = len(q)
            for _ in range(size):
                i = q.popleft()
                if i == len(arr) - 1:
                    return counter
                num = arr[i]
                neighbors = graph[num]
                for neighbor in neighbors:
                    if not visited[neighbor]:
                        q.append(neighbor)
                        visited[neighbor] = 1
                graph.pop(num)
                if i + 1 < len(arr) and not visited[i + 1]:
                    q.append(i + 1)
                    visited[i + 1] = 1
                if i - 1 >= 0 and not visited[i - 1]:
                    q.append(i - 1)
                    visited[i - 1] = 1
            counter += 1



class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        if len(arr)==1:
            return 0
        
        # prune duplicates
        i=0
        while i<len(arr)-2:
            if arr[i]==arr[i+1]==arr[i+2]:
                arr.pop(i)
            else:
                i+=1   
        
        def jump(i):
            nexts=[]
            if i-1>=0:
                nexts.append(i-1)
            if i+1<len(arr):
                nexts.append(i+1)
            for index in d[arr[i]]:
                #print('index', index)
                if index != i:
                    nexts.append(index)
            return nexts
                
                
        d={}
        for i in range(len(arr)-1, -1, -1):
            if arr[i] in d:
                d[arr[i]].add(i)
            else:
                d[arr[i]]={i} # value is set
        
        for k,v in list(d.items()):
            d[k]=list(v)
            d[k].sort(reverse=True)
        q=deque()
        
        visited=set()
        q.append(0)
        visited.add(0)
        steps=-1
        while q:
            size=len(q)
            steps +=1
            for i in range(size):
                pop_index=q.popleft()
                if pop_index==len(arr)-1:
                    return steps
                for nex in jump(pop_index):
                    if nex not in visited:
                        q.append(nex)
                        visited.add(nex)
        return -1
                
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
            


from collections import defaultdict,deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        g=defaultdict(list)
        
        for i,n in enumerate(arr):
            g[n].append(i)
        
        cur=[0]
        step=0
        seen={0}
        while cur:
            nex=[]
            for i in cur:
                if i==len(arr)-1:
                    return step
                for adj in g[arr[i]]:
                    if adj not in seen:
                        seen.add(adj)
                        nex.append(adj)
                g[arr[i]].clear()
                if i-1>=0 and i-1 not in seen:
                    seen.add(i-1)
                    nex.append(i-1)
                if i+1<len(arr) and i+1 not in seen:
                    seen.add(i+1)
                    nex.append(i+1)
            step+=1
            cur=nex
        return -1
            
#         idx=defaultdict(list)
#         for i,n in enumerate(arr):
#             if n in idx:
#                 for j in idx[n]:
#                     g[i].add(j)
#                     g[j].add(i)
#             idx[n].append(i)
#             if i>0:
#                 g[i].add(i-1)
#                 g[i-1].add(i)
        
#         q=deque([(0,0)])
#         seen=set()
#         while q:
#             i,step = q.popleft()
#             if i==len(arr)-1:
#                 return step
#             if i in seen:
#                 continue
#             seen.add(i)
#             for adj in g[i]:
#                 q.append((adj,step+1))


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0
        
        # intuition: BFS
        dic = {}
        for i, num in enumerate(arr):
            if num not in dic:
                dic[num] = set()
            dic[num].add(i)
        
        bag= set(list(range(1, len(arr))))
        queue = [0]
        res = 0
        print(bag)
        while len(queue) > 0:
            l = len(queue)
            for _ in range(l):
                node = queue.pop(0)
                if node == len(arr)-1:
                    return res
                # neighbors
                if node > 0:
                    if node-1 in bag:
                        queue.append(node-1)
                        bag.remove(node-1)
                        if arr[node-1] in dic and node-1 in dic[arr[node-1]]:
                            dic[arr[node-1]].remove(node-1)
                            if not dic[arr[node-1]]:
                                del dic[arr[node-1]]
                if node < len(arr) -1:
                    if node + 1 in bag:
                        queue.append(node+1)
                        bag.remove(node+1)
                        if arr[node-1] in dic and node-1 in dic[arr[node-1]]:
                            dic[arr[node-1]].remove(node-1)
                            if not dic[arr[node-1]]:
                                del dic[arr[node-1]]
                # SAME VALUE
                if arr[node] in dic:
                    for i in dic[arr[node]]:    
                        if i in bag:
                            bag.remove(i)
                            queue.append(i)
                    del dic[arr[node]]
            res += 1
                
                    
                
                        
            


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        '''
        #最短就利用BFS
        '''
        n=len(arr)
        g=collections.defaultdict(list)
        for i,v in enumerate(arr):
            g[v].append(i)
        #存放同值的位置
        visit=[0]*n
        values=set()
        step=0
        q=[0]
        while q:
            size=len(q)
            for _ in range(size):
                cur=q.pop(0)
                if cur==n-1:
                    return step
                for i in [cur-1,cur+1]:
                    if 0<=i<n and not visit[i]:
                        visit[i]=1
                        q.append(i)
                if arr[cur] not in values:
                    values.add(arr[cur])
                    for i in g[arr[cur]]:
                        if not visit[i]:
                            visit[i]=1
                            q.append(i)
            step+=1
        return step

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        v_jumped = set()
        v_idx = collections.defaultdict(list)
        for i,v in enumerate(arr):
            v_idx[v].append(i)
        
        q = [0]
        seen_idx = {0}
        
        step = 0
        while q:
            sz = len(q)
            for _ in range(sz):
                i = q.pop(0)
                if i == len(arr)-1:
                    return step
                if arr[i] not in v_jumped:
                    v_jumped.add(arr[i])
                    for j in v_idx[arr[i]]:
                        if j not in seen_idx:
                            seen_idx.add(j)
                            q.append(j)
                if i + 1 < len(arr) and i+1 not in seen_idx:
                    seen_idx.add(i+1)
                    q.append(i+1)
                if i-1 >= 0 and i-1 not in seen_idx:
                    seen_idx.add(i-1)
                    q.append(i-1)
            step += 1
        return -1
        


class Solution:
    def minJumps(self, arr):
        n = len(arr)
        if n == 1: return 0 
        d = defaultdict(list)
        for i,val in enumerate(arr):
            d[val].append(i)
        visited = set([0])
        check = set()
        stack = [0]
        k, jumps = len(stack), 1
        while stack:
            i = stack.pop(0)
            childs = [i-1,i+1] 
            if arr[i] not in check:
                childs += [j for j in d[arr[i]]]
                check.add(arr[i])
            childs = [j for j in childs if 0 <= j < n and j not in visited]
            childs = set(childs)
            for j in childs:
                if j == n-1: return jumps
                visited.add(j)
                stack.append(j)
            k -= 1
            if not k:
                k = len(stack)
                jumps += 1
        return jumps

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        def BFS(queue):
            seen , val_seen = [1]*len(arr) , set();seen[0] = 0
            while queue:
                var , level = queue.pop(0)
                if var == len(arr) - 1:return level
                if seen[var + 1]:queue.append([var+1,level+1]);seen[var+1] = 0
                if var - 1 >=0 and   seen[var - 1]:queue.append([var-1,level+1]);seen[var-1] = 0
                if arr[var] not in val_seen:  
                    for i in d[arr[var]]:
                        if seen[i]:queue.append([i,level+1]);seen[i] = 0
                val_seen.add(arr[var])
        
        d = defaultdict(list)
        for i , v in enumerate(arr):d[v] +=[i]
        return (BFS([[0,0]]))

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        g = collections.defaultdict(list)
        for i, num in enumerate(arr):
            g[num].append(i)
        visited = set()
        q = deque([(0,0)]) #idx,step
        
        while q:
            idx,step = q.popleft()
            if idx == len(arr)-1:
                return step
            visited.add(idx)
            for n_idx in [idx-1,idx+1]+ g[arr[idx]]:
                if n_idx not in visited and 0<=n_idx<len(arr):
                    q.append((n_idx,step +1))
            del g[arr[idx]]

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        record={}
        for idx,item in enumerate(arr,0):
            if item not in record:
                record[item]=[idx]
            else:
                if record[item][-1]+2>=idx:
                    record[item][-1]=idx
                else:
                    record[item].append(idx)
        queue=[0]
        ret=[-1]*len(arr)
        ret[0]=0
        step=0
        last=len(arr)-1
        while queue:
            target=[]
            step+=1
            for idx in queue:
                if idx>0 and ret[idx-1]==-1:
                    target.append(idx-1)
                    ret[idx-1]=step
                if idx+1<len(arr) and ret[idx+1]==-1:
                    target.append(idx+1)
                    ret[idx+1]=step
                    if idx+1==last:
                        return step
                for pos in record[arr[idx]]:
                    if pos==idx:
                        continue
                    if ret[pos]==-1:
                        target.append(pos)
                        ret[pos]=step
                        if pos==last:
                            return step
            queue=target
        return ret[-1]

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        dic = collections.defaultdict(list)
        for i, num in enumerate(arr):
            dic[num].append(i)
        queue = [0]
        pos_visited = set([0])
        num_visited = set()
        step = 0
        while queue:
            for _ in range(len(queue)):
                cur = queue.pop(0)
                if cur == n - 1:
                    return step
                for nextIdx in [cur - 1, cur + 1] + dic[arr[cur]] * (arr[cur] not in num_visited):
                    if 0 <= nextIdx < n and nextIdx not in pos_visited:
                        pos_visited.add(nextIdx)
                        queue.append(nextIdx)
                num_visited.add(arr[cur])
            step += 1
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        N = len(arr)
        last_idx = N - 1
        indices = collections.defaultdict(set)

        for i, a in enumerate(arr):
            indices[a].add(i)

        moves = [None] * N
        moves[0] = 0
        edges = []
        idx = 0
        seen_values = set()

        def reachables(i):
            idx_set = set()
            if arr[i] not in seen_values:
                seen_values.add(arr[i])
                idx_set |= indices[arr[i]]
            if i-1 >= 0:
                idx_set.add(i-1)
            if i+1 < N:
                idx_set.add(i+1)
            if i in idx_set:
                idx_set.remove(i)
            return idx_set

        while idx != last_idx:
            for j in reachables(idx):
                if moves[j] is None:
                    heapq.heappush(edges, (moves[idx]+1, j))

            move, idx = heapq.heappop(edges)
            moves[idx] = move

        return moves[idx]

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        seen = { 0 }
        q = [0]
        goal = len(arr) - 1
        
        linked = collections.defaultdict(list)
        for idx, x in enumerate(arr):
            linked[x].append(idx)
            
            
        q_back = [goal]
        q = [0]
        levels = -1
        
        while q:
            levels += 1
            q_len = len(q)
            for _ in range(q_len):
                idx = q.pop(0)

                if idx == goal:
                    
                    return levels
                
                if idx + 1 not in seen:
                    q.append(idx + 1)
                    seen.add(idx + 1)
                    
                if idx > 0  and idx - 1 not in seen:
                    q.append(idx - 1)
                    seen.add(idx - 1)
                    
                for link in linked[arr[idx]]:
                    if link not in seen:
                        q.append(link)
                        seen.add(link)
                        
                del linked[arr[idx]]
                        
                


class Solution:
    def minJumps(self, nums):
        neighbors = defaultdict(list)
        _ = [neighbors[num].append(i) for i, num in enumerate(nums)]
        q = deque([(0, 0)])
        num_seen, pos_seen = set(), set()
        while q:
            pos, step = q.popleft()
            if pos == len(nums) - 1:
                return step
            num = nums[pos]
            pos_seen.add(pos)
            for p in [pos - 1, pos + 1] + neighbors[num] * (num not in num_seen):
                if p in pos_seen or not 0 <= p < len(nums):
                    continue
                q.append((p, step + 1))

            num_seen.add(num)

from collections import defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        '''
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]

        curs = [0]  # store current layers
        visited = {0}
        step = 0

        # when current layer exists
        while curs:
            nex = []

            # iterate the layer
            for node in curs:
                # check if reached end
                if node == n-1:
                    return step

                # check same value
                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                graph[arr[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1
        '''
        # we start from index one and perform a bfs
        # in order to perform bfs properly we create a mapping from number to all the indices the number is encountered
        m = defaultdict(list)
        for i in range(len(arr)):
            m[arr[i]].append(i)
        start = (0,0)
        queue = [start]
        visited = set([0])
        while queue != []:
            current = queue.pop(0)
            # print(current,queue)
            if current[0] == len(arr)-1:
                return current[1]
            if current[0] + 1 < len(arr) and current[0] + 1 not in visited:
                queue.append((current[0]+1,current[1]+1))
                visited.add(current[0] + 1)
            if current[0] - 1 >= 0 and current[0] - 1 not in visited:
                queue.append((current[0]-1,current[1]+1))
                visited.add(current[0] - 1)
            for n in m[arr[current[0]]]:
                if n not in visited:
                    queue.append((n,current[1] + 1))
                    visited.add(n)
            if arr[n] in m:
                del m[arr[n]]
        


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        def BFS(queue):
            seen , val_seen = [1]*len(arr) , set();seen[0] = 0
            while queue:
                var , level = queue.pop(0)
                if var == len(arr) - 1:return level
                if seen[var + 1]:queue.append([var+1,level+1]);seen[var+1] = 0
                if var - 1 >=0 and   seen[var - 1]:queue.append([var-1,level+1]);seen[var-1] = 0
                if arr[var] not in val_seen:  
                    for i in d[arr[var]]:
                        if seen[i]:queue.append([i,level+1]);seen[i] = 0
                val_seen.add(arr[var])
        
        d = defaultdict(list)
        for i in range(len(arr)):d[arr[i]] +=[i]
        return (BFS([[0,0]]))

from collections import defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:        
        pos_m = defaultdict(set)        
        for idx, val in enumerate(arr):
            pos_m[val].add(idx)
        visited = [float('inf') for i in range(len(arr))]
        seen = set([0])        
        steps = 0
        pos_m[arr[0]].remove(0)
        
        # (idx, step)
        q = [(0, 0)]
        while q:
            for _ in range(len(q)):
                idx, step = q.pop(0)
                if idx == len(arr)-1:
                    return step
                if idx > 0 and idx-1 not in seen:
                    seen.add(idx-1)
                    q.append((idx-1, step+1))
                if idx+1 < len(arr) and idx+1 not in seen:
                    seen.add(idx+1)
                    q.append((idx+1, step+1))
                # pos_to_remove = []
                for pos in pos_m[arr[idx]]:
                    if pos not in seen:
                        seen.add(pos)
                        q.append((pos, step+1))                    
                        # pos_to_remove.append(pos)
                del pos_m[arr[idx]]
                # for pos in pos_to_remove:
                #     pos_m[arr[idx]].remove(pos)
                        
        return -1
        
            
                


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        nei = collections.defaultdict(list)
        _ = [nei[x].append(i) for i, x in enumerate(arr)]

        frontier = collections.deque([(0,0)])
        num_met, pos_met = set(), set()
        while frontier:
            pos, step = frontier.popleft() # state: position, step
            if pos == len(arr) - 1: return step
            num = arr[pos]
            pos_met.add(pos) # track explored positions

            for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
                if p in pos_met or not 0 <= p < len(arr): continue
                frontier.append((p, step + 1))

            num_met.add(num) # track explored values
       


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # return self.bfs(arr)
        return self.minJumpsBiBFS(arr)
    def bfs(self, arr: List[int]):
        arrLen = len(arr)
        if arrLen <= 1:
            return 0
        adjList = defaultdict(set)
        for i in range(len(arr)):
            adjList[arr[i]].add(i)
        queue = deque([0])
        visited = set([0])
        jump = 0
        
        while queue:
            length = len(queue)
            
            for _ in range(length):
                node = queue.popleft()
                for nei in adjList[arr[node]]:
                    if nei == arrLen-1:
                        return jump+1
                    if nei in visited:
                        continue
                    visited.add(nei)
                    queue.append(nei)
                adjList[arr[node]].clear()
                    
                if node + 1 < arrLen:
                    if node + 1 == arrLen-1:
                        return jump+1
                    if node + 1 not in visited:
                        visited.add(node + 1)
                        queue.append(node + 1)
                    
                if node -1 >= 0:
                    if node - 1 == arrLen-1:
                        return jump+1
                    if node - 1 not in visited:
                        visited.add(node - 1)
                        queue.append(node - 1)
            jump += 1
        return -1
                
            
        
    def minJumpsBiBFS(self, arr: List[int]) -> int:
        arrLen = len(arr)
        if arrLen <= 1:
            return 0
        adjList = defaultdict(set)
        for i in range(len(arr)):
            adjList[arr[i]].add(i)
        frontQueue = deque([0])
        rearQueue = deque([len(arr)-1])
        visited = set([0])
        jump = 0
        
        while frontQueue or rearQueue:
            if len(frontQueue) > len(rearQueue):
                frontQueue, rearQueue = rearQueue, frontQueue
            length = len(frontQueue)
            
            for _ in range(length):
                node = frontQueue.popleft()
                for nei in adjList[arr[node]]:
                    if nei in rearQueue:
                        return jump+1
                    if nei in visited:
                        continue
                    visited.add(nei)
                    frontQueue.append(nei)
                adjList[arr[node]].clear()
                  
                if node + 1 < arrLen:
                    if node + 1 in rearQueue:
                        return jump+1
                    if node + 1 not in visited:
                        visited.add(node + 1)
                        frontQueue.append(node + 1)
                    
                if node -1 >= 0:
                    if node - 1 in rearQueue:
                        return jump+1
                    if node - 1 not in visited:
                        visited.add(node - 1)
                        frontQueue.append(node - 1)
            jump += 1
        return -1
                    


class Solution:
    def minJumps(self, arr) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]

        curs = [0]  # store layers from start
        visited = {0, n-1}
        step = 0

        other = [n-1] # store layers from end

        # when current layer exists
        while curs:
            # search from the side with fewer nodes
            if len(curs) > len(other):
                curs, other = other, curs
            nex = []

            # iterate the layer
            for node in curs:

                # check same value
                for child in graph[arr[node]]:
                    if child in other:
                        return step + 1
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                #graph[arr[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if child in other:
                        return step + 1
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0
        else:
            num_indices = defaultdict(list)
            for i in range(len(arr) - 1, -1, -1):
                num_indices[arr[i]].append(i)
            visited = {0}
            queue = deque()
            queue.append((0, 0))
            while queue:
                i, steps = queue.popleft()
                for j in [i - 1, i + 1] + num_indices[arr[i]]:
                    if j not in visited and 0 <= j < len(arr):
                        if j == len(arr) - 1:
                            return steps + 1
                        else:
                            queue.append((j, steps + 1))
                            visited.add(j)

from collections import defaultdict
from collections import deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0

        indexes = defaultdict(list)

        for i, v in enumerate(arr):
            if i == 0 or arr[i - 1] != v:
                indexes[v].append(i)

        queue = deque([(0, True), (len(arr) - 1, False)])
        minimum_steps = {0:0}
        minimum_steps_negative = {len(arr) - 1:0}
        while queue:
            curPos, direction = queue.popleft()

            if direction and curPos in minimum_steps_negative:
                return minimum_steps_negative[curPos] + minimum_steps[curPos]
            if not direction and curPos in minimum_steps:
                return minimum_steps_negative[curPos] + minimum_steps[curPos]

            candidates = []

            if curPos > 0:
                candidates.append(curPos - 1)
            if curPos < len(arr) - 1:
                candidates.append(curPos + 1)
            candidates.extend(indexes[arr[curPos]])

            ans = []
            for i in candidates:
                if direction:
                    checker = minimum_steps
                else:
                    checker = minimum_steps_negative

                if i not in checker:
                    checker[i] = checker[curPos] + 1
                    queue.append((i, direction))

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0
        
        arr_f = []
        prev = None
        repeat = 0
        for num in arr:
            if num == prev:
                if repeat == 2:
                    continue
                repeat += 1
            else:
                prev = num
                repeat = 0
            arr_f.append(num)
        n = len(arr_f)

        graph = {}
        for i in range(n):
            if arr_f[i] in graph:
                graph[arr_f[i]].append(i)
            else:
                graph[arr_f[i]] = [i]

        curs = [0]  # store current layers
        visited = {0}
        step = 0

        # when current layer exists
        while curs:
            nex = []

            # iterate the layer
            for node in curs:
                # check if reached end
                if node == n-1:
                    return step

                # check same value
                for child in graph[arr_f[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                graph[arr_f[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if 0 <= child < n and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        map = collections.defaultdict(list)
        for i, a in enumerate(arr):
            map[a].append(i)
        
        visited, visiting = {-1}, {0}
        for steps in itertools.count():
            visited |= visiting
            if len(arr) - 1 in visited:
                return steps
            visiting = {j for i in visiting for j in [i - 1, i + 1] + map.pop(arr[i], [])} - visited

from collections import deque

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        # construct graph
        n = len(arr)
        graph = collections.defaultdict(list)
        for i, num in enumerate(arr):
            graph[num].append(i)
        
        # bfs
        queue = deque([0])
        visited = set([0])
        
        steps = 0
        while queue:
            level_size = len(queue)
            for _ in range(level_size):
                curr_idx = queue.popleft()
                if curr_idx == n - 1:
                    return steps
                for nxt_idx in [curr_idx - 1, curr_idx + 1] + graph[arr[curr_idx]][::-1]:
                    if 0 <= nxt_idx < n and nxt_idx not in visited:
                        if nxt_idx == n - 1:
                            return steps + 1
                        queue.append(nxt_idx)
                        visited.add(nxt_idx)
            steps += 1
            
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # return self.bfs(arr)
        return self.minJumpsBiBFS(arr)
    def bfs(self, arr: List[int]):
        arrLen = len(arr)
        if arrLen <= 1:
            return 0
        adjList = defaultdict(set)
        for i in range(len(arr)):
            adjList[arr[i]].add(i)
        queue = deque([0])
        visited = set([0])
        jump = 0
        
        while queue:
            length = len(queue)
            
            for _ in range(length):
                node = queue.popleft()
                for nei in adjList[arr[node]]:
                    if nei == arrLen-1:
                        return jump+1
                    if nei in visited:
                        continue
                    visited.add(nei)
                    queue.append(nei)
                adjList[arr[node]].clear()
                    
                if node + 1 < arrLen:
                    if node + 1 == arrLen-1:
                        return jump+1
                    if node + 1 not in visited:
                        visited.add(node + 1)
                        queue.append(node + 1)
                    
                if node -1 >= 0:
                    if node - 1 == arrLen-1:
                        return jump+1
                    if node - 1 not in visited:
                        visited.add(node - 1)
                        queue.append(node - 1)
            jump += 1
        return -1
                
            
        
    def minJumpsBiBFS(self, arr: List[int]) -> int:
        arrLen = len(arr)
        if arrLen <= 1:
            return 0
        adjList = defaultdict(set)
        for i in range(len(arr)):
            adjList[arr[i]].add(i)
        frontQueue = deque([0])
        rearQueue = deque([len(arr)-1])
        visited = set([0])
        jump = 0
        
        while frontQueue or rearQueue:
            if len(frontQueue) > len(rearQueue):
                frontQueue, rearQueue = rearQueue, frontQueue
            length = len(frontQueue)
            
            for _ in range(length):
                node = frontQueue.popleft()
                for nei in adjList[arr[node]]:
                    if nei in rearQueue:
                        return jump+1
                    if nei in visited:
                        continue
                    visited.add(nei)
                    frontQueue.append(nei)
                    
                if node + 1 < arrLen:
                    if node + 1 in rearQueue:
                        return jump+1
                    if node + 1 not in visited:
                        visited.add(node + 1)
                        frontQueue.append(node + 1)
                    
                if node -1 >= 0:
                    if node - 1 in rearQueue:
                        return jump+1
                    if node - 1 not in visited:
                        visited.add(node - 1)
                        frontQueue.append(node - 1)
            jump += 1
        return -1
                    



class Solution:
    # bidirectional, best 416 ms, memory 99.90%
    def minJumps(self, arr):
        length = len(arr)
        # if no any connection in nodes, answer equals to array length - 1
        if len(set(arr)) == length: return length - 1
        if arr[0] == arr[-1]: return 1

        _map = defaultdict(set) # connection map
        for i, val in enumerate(arr): _map[val].add(i)

        # BFS, seen: visited index, visit: visited connection
        res, seen, visit = 0, {0}, set()
        # curs: nodes in current side level, other: nodes in opposite side
        curs, other = {0}, {length - 1}
        while curs:
            res += 1
            # store found nodes in this level
            thisLevel = set()
            for i in curs:
                # check move backwards 
                if i - 1 > 0 and i - 1 not in seen: 
                    thisLevel.add(i - 1)
                # check in place
                if arr[i] in _map:
                    thisLevel |= (_map[arr[i]] - seen) 
                    visit.add(arr[i])
                    del _map[arr[i]]
                # check move forwards
                if i + 1 < length and i + 1 not in seen: 
                    thisLevel.add(i + 1)

            # check if this level and the other side intersect
            if thisLevel & other: return res  

            # update current side for next round          
            curs = thisLevel
            # choose smaller side into next round 
            if len(curs) > len(other): curs, other = other, curs
            # if we don't exchange, put found nodes into seen
            # because they are found in current direction
            else: seen |= thisLevel

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1: return 0
        
        cost = 0
        size = len(arr)
        visited = [False] * size
        visited[0] = True
        
        same = collections.defaultdict(list)
        for p, n in enumerate(arr):
            same[n].append(p)
            
        st = [0] # contains same cost vals
        cost = 0
        
        while True:
            nxt = []
            cost += 1
            # print(st)
            while st:
                cur = st.pop()
                # print()
                for nei in same[arr[cur]] + [cur-1, cur+1]:
                    # print(nei, end=' ')
                    if nei == cur or not 0 <= nei < size:
                        continue
                    if nei == size - 1:
                        # print(st)
                        return cost
                    if not visited[nei]:
                        visited[nei] = True
                        nxt.append(nei)
            st = nxt
            
            
        
        


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        x=[]
        x.append(arr[0])
        for i in range(1,len(arr)-1):
            if arr[i]==arr[i-1] and arr[i]==arr[i+1]:
                continue
            else:
                x.append(arr[i])
        if len(arr)>1:
            x.append(arr[-1])
        arr=x
        d=collections.defaultdict(list)
        for i in range(len(arr)):
            d[arr[i]].append(i)
        bfs=[0]
        steps=0
        temp=[]
        seen=set([0])
        while len(bfs)>0:
            index = bfs.pop()
            if index==len(arr)-1:
                return steps
            if (index+1)<len(arr) and (index+1) not in seen:
                temp.append(index+1)
                seen.add(index+1)
            if (index-1)>=0 and (index-1) not in seen:
                temp.append(index-1)
                seen.add(index-1)
            for i in d[arr[index]]:
                if i not in seen:
                    temp.append(i)
                    seen.add(i)

            if len(bfs)==0:
                bfs=temp
                temp=[]
                steps+=1

        return steps
            


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        pos = defaultdict(list)
        for i, num in enumerate(arr):
            pos[num].append(i)
        
        q, steps = deque([0]), 0
        seen = [False]*n
        seen[0] = True
        while q:
            size = len(q)
            for _ in range(size):
                i = q.popleft()
                if i == n-1:
                    return steps
                # jump to i+1
                if i+1 < n and not seen[i+1]:
                    q.append(i+1)
                    seen[i+1] = True
                # jump to i-1
                if i-1 > -1 and not seen[i-1]:
                    q.append(i-1)
                    seen[i-1] = True
                # jump to j where arr[i] == arr[j]
                for j in pos[arr[i]]:
                    if not seen[j]:
                        q.append(j)
                        seen[j] = True
                pos[arr[i]].clear()
            steps += 1
        
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return 0
        if n == 2:
            return 1
        
        arr_f = []
        prev = None
        repeat = 0
        for num in arr:
            if num == prev:
                if repeat == 2:
                    continue
                repeat += 1
            else:
                prev = num
                repeat = 0
            arr_f.append(num)
        n = len(arr_f)
        
        idx_by_num = defaultdict(list)
        for i in range(n):
            idx_by_num[arr_f[i]].append(i)
        
        q = [(0, n-1)]
        visited = set([n-1])
        while q:
            step, cidx = q.pop(0)
            if cidx == 0:
                return step
            
            if cidx - 1 not in visited:
                visited.add(cidx - 1)
                q.append((step + 1, cidx - 1))
            if cidx + 1 < n and cidx + 1 not in visited:
                visited.add(cidx + 1)
                q.append((step + 1, cidx + 1))
            
            for same_v_idx in idx_by_num[arr_f[cidx]]:
                if same_v_idx not in visited:
                    visited.add(same_v_idx)
                    q.append((step + 1, same_v_idx))
            
        


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return 0
        if n == 2:
            return 1
        
        arr_f = []
        prev = None
        repeat = 0
        for num in arr:
            if num == prev:
                if repeat == 2:
                    continue
                repeat += 1
            else:
                prev = num
                repeat = 0
            arr_f.append(num)
        n = len(arr_f)
        
        idx_by_num = defaultdict(list)
        for i in range(n):
            idx_by_num[arr_f[i]].append(i)
        
        q = [(0, n-1)]
        visited = set([n-1])
        while q:
            step, cidx = q.pop(0)
            if cidx == 0:
                return step
            
            if cidx - 1 not in visited:
                visited.add(cidx - 1)
                q.append((step + 1, cidx - 1))
            if cidx + 1 < n and cidx + 1 not in visited:
                visited.add(cidx + 1)
                q.append((step + 1, cidx + 1))
            
            for same_v_idx in idx_by_num[arr_f[cidx]]:
                if same_v_idx not in visited:
                    visited.add(same_v_idx)
                    q.append((step + 1, same_v_idx))
            
            idx_by_num[arr_f[cidx]].clear()
            
        


# https://leetcode.com/problems/jump-game-iv/discuss/774915/Python-Easy!-BFS-Solution-oror-Time-Complexity%3A-O(n)
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0
        
        d = collections.defaultdict(list)
        for index, element in enumerate(arr):
            d[element].append(index)

        queue = deque([(0, 0)])
        s = set([0])

        while len(queue):
            currIndex, jumps = queue.popleft()

            for nextIndex in [currIndex - 1, currIndex + 1] + d[arr[currIndex]][::-1]:
                if nextIndex < len(arr) and nextIndex >= 0 and nextIndex != currIndex and nextIndex not in s:
                    if nextIndex == len(arr) - 1:
                        return jumps + 1
                    s.add(nextIndex)
                    queue.append((nextIndex, jumps + 1))

        return -1


# https://leetcode.com/problems/jump-game-iv/discuss/774915/Python-Easy!-BFS-Solution-oror-Time-Complexity%3A-O(n)
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0
        
        d = collections.defaultdict(list)
        for index, element in enumerate(arr):
            d[element].append(index)

        queue = collections.deque([(0, 0)])
        s = set()
        s.add(0)

        while len(queue):
            currIndex, jumps = queue.popleft()

            for nextIndex in [currIndex - 1, currIndex + 1] + d[arr[currIndex]][::-1]:
                if nextIndex < len(arr) and nextIndex >= 0 and nextIndex != currIndex and nextIndex not in s:
                    if nextIndex == len(arr) - 1:
                        return jumps + 1
                    s.add(nextIndex)
                    queue.append((nextIndex, jumps + 1))

        return -1


# from collections import deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i,val in enumerate(arr):
            graph[val].append(i)
            
        def dfs():
            queue = deque() # or we could also write it as deque([])
            queue.append((0,0))# start index ,steps(level)
            seen={0}
            
            while queue:
                i,d= queue.popleft()
                if i==len(arr)-1:
                    return(d)
                
                for j in [i-1,i+1]+ graph[arr[i]][::-1] : # not reversing the array will TLE, even though its correct, cause it will again do BFS on ith index instead of trying other ones first
                    if 0<=j<len(arr) and j not in seen and j!=i:
                        seen.add(j)
                        if j==len(arr)-1: # again this part is imp otherwise it will TLE
                            return(d+1)
                        queue.append((j,d+1))
        
        return( dfs() )
    
#         q = deque([[0, 0]])
#         d = defaultdict(list)
#         vis = set([0])
#         for i,val in enumerate(arr):
#             d[val].append(i)
        
#         while q:
#             idx, steps = q.popleft()
#             if idx == len(arr)-1:
#                 return steps
#             for i in d.pop(arr[idx], [])+[idx+1, idx-1]:
#                 if i not in vis and i >= 0:
#                     vis.add(i)
#                     q.append([i, steps + 1])


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) <= 1:
            return 0
        bfs = []
        heapq.heappush(bfs, (0,0))
        seen = {}
        seen[0] = 0
        G = defaultdict(list)
        for i, a in enumerate(arr):
            G[a].append(i)
        while bfs:
            step, idx = heapq.heappop(bfs)
            idx = -idx
            for d in (-1, 1):
                nidx = idx + d
                if nidx >= 0 and nidx < len(arr):
                    if nidx not in seen or seen[nidx] > step + 1:
                        if nidx == len(arr) - 1:
                            return step + 1
                        seen[nidx] = step + 1
                        heapq.heappush(bfs, (step + 1, -nidx))
            for d in G[arr[idx]][::-1]:
                if d not in seen or seen[d] > step + 1:
                    if d == len(arr) - 1:
                        return step + 1
                    seen[d] = step + 1
                    heapq.heappush(bfs, (step + 1, -d))
        return -1

from collections import defaultdict, deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) <= 1:
            return 0
        mapping = defaultdict(list)
        for idx, val in enumerate(arr):
            mapping[val].append(idx)
        visited = set()
        que = deque()
        que.append((0, 0))
        visited.add(0)
        m = len(arr)
        while que:
            top = que.popleft()
            idx, depth = top[0], top[1]
            if idx + 1 < m and (idx+1) not in visited:
                if idx+1  == (m-1):
                    return depth + 1
                visited.add(idx+1)
                que.append((idx+1, depth+1))
            if idx-1 >= 0 and (idx-1) not in visited:
                visited.add(idx-1)
                que.append((idx-1, depth+1))
            for neigh in mapping[arr[idx]]:
                if neigh not in visited:
                    if  neigh == m-1:
                        return depth+1
                    visited.add(neigh)
                    que.append((neigh, depth+1))
            mapping.pop(arr[idx])
        return -1

from collections import *
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) <= 1:
            return 0
        mapper = defaultdict(set)
        for i, x in enumerate(arr):
            mapper[x].add(i)
        end = len(arr) - 1
        queue = deque([(arr[0],0,0)])
        vis = set()
        vis.add(0)
        while queue:
            # print(queue)
            num, index, count = queue.popleft()
            if index == end:
                return count
            if num in mapper:
                for y in mapper.pop(num):
                    if y not in vis:
                        queue.append((arr[y],y,count + 1))
                        vis.add(y)
            if index+1 <= end and index + 1 not in vis:
                queue.append((arr[index+1],index+1,count + 1))
                vis.add(index+1)
            if index-1 >= 0 and index - 1 not in vis:
                queue.append((arr[index-1],index-1,count + 1))
                vis.add(index-1)


class Solution:
    def minJumps(self, arr):
        length = len(arr)
        if len(set(arr)) == length: return length - 1
        if arr[0] == arr[-1]: return 1

        _map = defaultdict(set) # connection map
        for i, val in enumerate(arr): _map[val].add(i)

        res, seen, visit = 0, {0}, set()
        curs, other = {0}, {length - 1}
        while curs:
            res += 1

            thisLevel = set()
            for i in curs:
                if i - 1 > 0 and i - 1 not in seen: 
                    thisLevel.add(i - 1)
                if arr[i] in _map:
                    thisLevel |= (_map[arr[i]] - seen) 
                    visit.add(arr[i])
                    del _map[arr[i]]
                if i + 1 < length and i + 1 not in seen: 
                    thisLevel.add(i + 1)

            if thisLevel & other: return res          
            curs = thisLevel
            if len(curs) > len(other): curs, other = other, curs
            else: seen |= thisLevel

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]

        curs = [0]  # store current layers
        visited = {0}
        step = 0

        # when current layer exists
        while curs:
            nex = []

            # iterate the layer
            for node in curs:
                # check if reached end
                if node == n-1:
                    return step

                # check same value
                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                graph[arr[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr:
            return 0
        #construct graph
        valueIndex = collections.defaultdict(list)
        for i, a in enumerate(arr):
            valueIndex[a].append(i)
        
#         graph = collections.defaultdict(list)
#         for i in range(len(arr)):
#             neighbor = []
#             if i > 0:
#                 neighbor.append(i-1)
#             if i < len(arr) - 1:
#                 neighbor.append(i+1)
#             sameValueIndices = valueIndex[arr[i]]
#             for idx in sameValueIndices:
#                 if idx != i:
#                     neighbor.append(idx)
#             graph[i] = neighbor
        
        #BFS
        queue = collections.deque([0])
        visited = {0 : 0}
        visitedValues = set()
        while queue:
            head = queue.popleft()
            #print(f\"head={head}\")
            if head == len(arr) - 1:
                return visited[head]
            
            shortNeighbor = [head - 1, head + 1]
            for neighbor in shortNeighbor:
                if 0 <= neighbor < len(arr) and not neighbor in visited:
                    visited[neighbor] = visited[head] + 1
                    queue.append(neighbor)
                
            if arr[head] not in visitedValues:
                visitedValues.add(arr[head])
                for neighbor in valueIndex[arr[head]]:
                    if neighbor not in visited:
                        visited[neighbor] = visited[head] + 1
                        queue.append(neighbor)
            
        return visited[len(arr) - 1]
                
            
            
        


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        q = deque([[0, 0]])
        d = defaultdict(list)
        vis = set([0])
        for i,val in enumerate(arr):
            d[val].append(i)
        
        while q:
            idx, steps = q.popleft()
            if idx == len(arr)-1:
                return steps
            for i in d.pop(arr[idx], [])+[idx+1, idx-1]:
                if i not in vis and i >= 0:
                    vis.add(i)
                    q.append([i, steps + 1])

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # Similar concept to jump game3, but here we need to find the minimum
        # jumps so we need to use queue instead of stack, also we need to use
        # hashmap to handle the third jump of mirror values
        
        # Base Case - No jumps needed
        if len(arr) == 1:
            return 0
        
        # Data Structure Declaration
        q = collections.deque()
        seen = set()
        hashmap = collections.defaultdict(list)
        destination = len(arr)-1
        minJumps = 0
        
        # Store mirrors in hashmap
        for index, num in enumerate(arr):
            hashmap[num].append(index)
        

        # Traversal start points
        q.append(0)
        seen.add(0)

        # Run loop until we have values in queue
        while q:
            
            sizeQ = len(q)
            
            # Traverse the queue level by level
            for i in range(sizeQ):
                Pos = q.popleft()
                # Check for destination
                if Pos == destination:
                    return minJumps
                
                # Number of choices for Jumping
                nextPos = Pos + 1
                prevPos = Pos - 1
                mirrorPos = hashmap[arr[Pos]]
                
                # Add if nextPos is valid
                if nextPos >= 0 and nextPos < len(arr) and nextPos not in seen:
                    seen.add(nextPos)
                    q.append(nextPos)
                    
                # Add if prevPos is valid
                if prevPos >= 0 and prevPos < len(arr) and prevPos not in seen:
                    seen.add(prevPos)
                    q.append(prevPos)
                
                # Add if we have mirror elements present
                if mirrorPos:
                    for val in mirrorPos:
                        if val >= 0 and val < len(arr) and val not in seen:
                            seen.add(val)
                            q.append(val)
                    # Once current element is taken into account, delete from map
                    del hashmap[arr[Pos]]
            # for every level increase the number of Jumps
            minJumps += 1
        return minJumps

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) <= 1:
            return 0
        bfs = [0]
        seen = set()
        seen.add(0)
        G = defaultdict(list)
        for i, a in enumerate(arr):
            G[a].append(i)
        step = 0
        while bfs:
            cur, bfs = bfs, []
            for idx in cur:
                if idx == len(arr) - 1:
                    return step
                for d in (-1, 1):
                    nidx = idx + d
                    if nidx >= 0 and nidx < len(arr):
                        if nidx not in seen:
                            seen.add(nidx)
                            bfs.append(nidx)
                for d in G[arr[idx]]:
                    if d not in seen:
                        if d not in seen:
                            seen.add(d)
                            bfs.append(d)
                G.pop(arr[idx])
            step += 1
        return -1

from collections import defaultdict
from heapq import heappush, heappop

class Solution:
    def adjacent(self, arr, i, jumps):
        if i > 0:
            yield i - 1
        if i < len(arr) - 1:
            yield i + 1
        
        for j in jumps[arr[i]]:
            if i != j:
                yield j
        
    def minJumps(self, arr: List[int]) -> int:
        if not arr:
            return 0
        
        jumps = defaultdict(set)
        for i, v in enumerate(arr):
            if i == 0 or i == len(arr) - 1 or arr[i - 1] != v or arr[i + 1] != v:
                jumps[v].add(i)
        
        steps = {}
        
        pq = []
        heappush(pq, (0, 0))
        
        while pq:
            n, neg_i = heappop(pq)
            i = -neg_i
            
            if i == len(arr) - 1:
                return n
            
            for j in self.adjacent(arr, i, jumps):
                if j not in steps or steps[j] > n + 1:
                    steps[j] = n + 1
                    heappush(pq, (n + 1, -j))


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        from collections import deque,defaultdict
        d=defaultdict(set)
        q=deque([0])
        res=0
        last=len(arr)-1
        for i in range(len(arr)):
            d[arr[i]].add(i)
        d[arr[0]].remove(0)
        print(d)
        while q:
            for i in range(len(q)):
                e=q.popleft()
                if e==last:
                    return res
                if e-1>=0 and e-1 in d[arr[e-1]]:
                    q.append(e-1)
                    d[arr[e-1]].remove(e-1)
                if e+1<=last and e+1 in d[arr[e+1]]:
                    q.append(e+1)
                    d[arr[e+1]].remove(e+1)
                for n in d[arr[e]]:
                    q.append(n)
                d[arr[e]]=[]
            res+=1
        return res
                    


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        lim = len(arr)
        d = dict()
        
        for i in range(0,lim):
            if arr[i] in d:
                d[arr[i]].append(i)
            else:
                d[arr[i]]=[i]
        for x in d:
            d[x].sort(reverse=True)
        
        start = []
        a=[-1 for i in range(0,lim)]       
        start = [[0,0]]
        
        for x in d[arr[0]]:
            if x!=0:
                start.append([x,1])
                a[x]=1
        
        start.sort(key=lambda x: x[1])
        while 1!=-1:
            tmp = []
            
            for x in start:
                
                if x[0]==lim-1:
                    return x[1]
                if x[0]+1==lim-1:
                    return x[1]+1
                a[x[0]]=1
                if x[0]>0 and a[x[0]-1]==-1:
                    tmp.append([x[0]-1,x[1]+1])
                if a[x[0]+1]==-1:
                    tmp.append([x[0]+1,x[1]+1])
                for y in d[arr[x[0]]]:
                    
                    if a[y]==-1:
                        
                        tmp.append([y,x[1]+1])
              
            start = tmp
        
                
                


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        graph = {} ## 和上面的idxs是一样的
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]

        curs = [0]  # store current layers
        visited = {0}
        step = 0

        # when current layer exists
        while curs:
            nex = []

            # iterate the layer
            for node in curs: ## 用curs和nxt代替bfs里deque的作用
                # check if reached end
                if node == n-1:
                    return step

                # check same value
                for child in graph[arr[node]]:
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                graph[arr[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1

from collections import deque
from collections import defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1: return 0
        d = defaultdict(list)
        for i, num in enumerate(arr):
            d[num].append(i)
        length = len(arr)
        q = deque()
        level = 0
        q.append(0)
        s = set()
        s.add(0)
        while(len(q) > 0):
            size = len(q)
            while size > 0:
                top = q.popleft()
                # if top == length - 1:
                #     return level
                if top - 1 >= 0 and top - 1 not in s:
                    s.add(top-1)
                    q.append(top-1)
                if top + 1 < length and top + 1 not in s:
                    if top + 1 == length - 1:
                        return level + 1
                    s.add(top+1)
                    q.append(top+1)
                for i in range(len(d[arr[top]])):
                    idx = d[arr[top]][len(d[arr[top]]) - 1 - i]
                    if idx not in s:
                        if idx == length - 1:
                            return level + 1
                        q.append(idx)
                        s.add(idx)
                size -= 1
            level += 1
        return level
            
            


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        
        m = len(arr)
        seen = [False for _ in range(m)]
        q = deque()
        step = 0

        quick_jump_graph = {}

        for i in range(len(arr)):
            if arr[i] in quick_jump_graph:
                quick_jump_graph[arr[i]].append(i)
            else:
                quick_jump_graph[arr[i]] = [i]

        q.append(0)

        while(len(q)):
            s = len(q)
            for i in range(s):
                cur_idx = q.popleft()
                if cur_idx < 0 or cur_idx >= m or seen[cur_idx]:
                    continue
                elif cur_idx == m - 1:
                    return step
                else:
                    seen[cur_idx] = True
                    q.append(cur_idx + 1)
                    q.append(cur_idx - 1)
                    if len(quick_jump_graph[arr[cur_idx]]) != 0:
                        for num in quick_jump_graph[arr[cur_idx]]:
                            q.append(num)
                        quick_jump_graph[arr[cur_idx]] = []
            step += 1
    
        return -1

from collections import deque,defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        idxs=defaultdict(set)
        for idx,e in enumerate(arr):
            idxs[e].add(idx)
        def bfs(idx):
            q=deque([0])
            step=-1
            not_visited=set(range(len(arr)-1,0,-1))
            while q:
                step+=1
                for _ in range(len(q)):
                    node=q.popleft()
                    if node==len(arr)-1:
                        return step
                    nxt_nodes=idxs[arr[node]]
                    nxt_nodes=not_visited&nxt_nodes
                    for nxt in [node-1,node+1]:
                        if nxt in not_visited:
                            nxt_nodes.add(nxt)
                    if len(arr)-1 in nxt_nodes:
                        return step+1
                    not_visited.difference_update(nxt_nodes)
                    nxt_nodes=sorted(nxt_nodes,reverse=True)
                    q.extend(nxt_nodes)
            return -1
        return bfs(0)


class Solution:
    def minJumps_tle(self, arr: List[int]) -> int:
        if not arr:
            return 0

        visited, L, lookup = set(), len(arr), collections.defaultdict(list)
        que = collections.deque()
        que.append((0, 0))
        visited.add(0)

        for k, v in enumerate(arr):
            lookup[v].append(k)

        while que:
            c, s = que.popleft()
            if c == L - 1:
                return s
            if c + 1 not in visited and c + 1 < L:
                visited.add(c + 1)
                que.append((c + 1, s + 1))
            if L > c - 1 >= 0 and c - 1 not in visited:
                visited.add(c - 1)
                que.append((c - 1, s + 1))
            for i in lookup[arr[c]]:
                if i == c:
                    continue
                if i not in visited and 0 <= i < L:
                    visited.add(i)
                    que.append((i, s + 1))

        return -1

    def minJumps(self, arr: List[int]) -> int:
        if not arr:
            return 0

        visited, L, lookup = set(), len(arr), collections.defaultdict(list)
        que = collections.deque()
        que.append(0)
        visited.add(0)

        for k, v in enumerate(arr):
            lookup[v].append(k)
        step = 0

        while que:
            size = len(que)

            for i in range(size):
                c = que.popleft()
                if c == L - 1:
                    return step

                if c + 1 not in visited and 0 <= c + 1 < L:
                    visited.add(c + 1)
                    que.append(c+1)
                if L > c - 1 >= 0 and c - 1 not in visited:
                    visited.add(c - 1)
                    que.append(c-1)
                for i in lookup[arr[c]]:
                    if i == c:
                        continue
                    if i not in visited and 0 <= i < L:
                        visited.add(i)
                        que.append(i)
                del lookup[arr[c]]
            step += 1

        return -1





class Solution:
    def minJumps(self, arr: List[int]) -> int:
        q = deque([[0, 0]])
        d = defaultdict(list)
        vis = set([0])
        for i,val in enumerate(arr):
            d[val].append(i)
        
        while q:
            idx, steps = q.popleft()
            if idx == len(arr)-1:
                return steps
            for i in d.pop(arr[idx], [])+[idx+1, idx-1][::-1]:
                if i not in vis and i >= 0:
                    vis.add(i)
                    q.append([i, steps + 1])

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # dp (forward backward pass) didn't work
        # from solution, do bfs
        # but add mirror positions as neighbors
        n = len(arr)
        
        mirrors = collections.defaultdict(list)
        _ = [mirrors[x].append(i) for i,x in enumerate(arr)]
        
        visited = set()
        q = collections.deque([(0,0)])
        while q:
            idx, jump = q.popleft()
            if idx == n - 1:
                return jump
            
            for nei in [idx-1, idx+1] + mirrors[arr[idx]]:
                if 0 <= nei < n and nei not in visited:
                    visited.add(nei)
                    q.append((nei, jump + 1))
            del mirrors[arr[idx]] # dont consider it from its neighbors again

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr:
            return 0

        visited, L, lookup = set(), len(arr), collections.defaultdict(list)
        que = collections.deque()
        que.append((0, 0))
        visited.add(0)

        for k, v in enumerate(arr):
            lookup[v].append(k)

        while que:
            c, s = que.popleft()
            if c == L - 1:
                return s
            if c + 1 not in visited and c + 1 < L:
                visited.add(c + 1)
                que.append((c + 1, s + 1))
            if L > c - 1 >= 0 and c - 1 not in visited:
                visited.add(c - 1)
                que.append((c - 1, s + 1))
            for i in lookup[arr[c]]:
                if i == c:
                    continue
                if i not in visited and 0 <= i < L:
                    visited.add(i)
                    que.append((i, s + 1))
            del lookup[arr[c]]

        return -1

    def minJumps_2(self, arr: List[int]) -> int:
        if not arr:
            return 0

        visited, L, lookup = set(), len(arr), collections.defaultdict(list)
        que = collections.deque()
        que.append(0)
        visited.add(0)

        for k, v in enumerate(arr):
            lookup[v].append(k)
        step = 0

        while que:
            size = len(que)

            for i in range(size):
                c = que.popleft()
                if c == L - 1:
                    return step

                if c + 1 not in visited and 0 <= c + 1 < L:
                    visited.add(c + 1)
                    que.append(c + 1)
                if L > c - 1 >= 0 and c - 1 not in visited:
                    visited.add(c - 1)
                    que.append(c - 1)
                for i in lookup[arr[c]]:
                    if i == c:
                        continue
                    if i not in visited and 0 <= i < L:
                        visited.add(i)
                        que.append(i)
                # review, if I comment out this one, I would get TLE, for test case [7,7,7..7], it would repeat the check
                # `if i not in visited and 0 <= i < L`
                del lookup[arr[c]]
            step += 1

        return -1




from collections import deque,defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        idxs=defaultdict(set)
        for idx,e in enumerate(arr):
            idxs[e].add(idx)
        def bfs(idx):
            q=deque([0])
            step=-1
            not_visited=set(range(len(arr)-1,0,-1))
            while q:
                step+=1
                for _ in range(len(q)):
                    node=q.popleft()
                    if node==len(arr)-1:
                        return step
                    nxt_nodes=idxs[arr[node]]
                    nxt_nodes=not_visited&nxt_nodes
                    for nxt in [node-1,node+1]:
                        if nxt in not_visited:
                            nxt_nodes.add(nxt)
                    if len(arr)-1 in nxt_nodes:
                        return step+1
                    not_visited.difference_update(nxt_nodes)
                    nxt_nodes=sorted(nxt_nodes,reverse=True)
                    q.extend(nxt_nodes)
            return -1
        bfs(0)
        return bfs(0)


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        visited = {0}
        lookup = defaultdict(list)
        for i, val in enumerate(arr):
            lookup[val].append(i)
        
        deq = deque([(0,0)])
        
        while deq:
            i, step = deq.popleft()
            if i == len(arr) - 1:
                return step
            nxt_idx = [i-1, i+1]
            nxt_idx.extend(lookup[arr[i]])
            lookup[arr[i]] = []
            for nxt in nxt_idx:
                if 0 <= nxt < len(arr) and nxt not in visited:
                    deq.append((nxt,step+1))
                    visited.add(nxt)
        return 0

from collections import defaultdict
from collections import deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:        
        pos_m = defaultdict(set)        
        for idx, val in enumerate(arr):
            pos_m[val].add(idx)
        visited = [float('inf') for i in range(len(arr))]
        seen = set([0])        
        steps = 0
        pos_m[arr[0]].remove(0)
        
        # (idx, step)        
        q = deque()
        q.append((0,0))
        while q:
            for _ in range(len(q)):
                idx, step = q.popleft()
                if idx == len(arr)-1:
                    return step
                if idx > 0 and idx-1 not in seen:
                    seen.add(idx-1)
                    q.append((idx-1, step+1))
                if idx+1 < len(arr) and idx+1 not in seen:
                    seen.add(idx+1)
                    q.append((idx+1, step+1))
                for pos in pos_m[arr[idx]]:
                    if pos not in seen:
                        seen.add(pos)
                        q.append((pos, step+1))                    
                del pos_m[arr[idx]]
                        
        return -1
        
            
                


class Solution:
    def minJumps(self, arr: List[int]) -> int:
#         graph = defaultdict(list)
#         for i in range(len(arr)):
#             graph[arr[i]].append(i)
            
#         visited = set()
#         src,dest = 0,len(arr)-1
#         queue = deque()
#         queue.append((src,0))
#         visited.add(src)
        
#         while queue:
#             node,dist = queue.popleft()
#             if node == dest:
#                 return dist
#             nextLayer = [node-1, node+1] + graph[arr[node]]
            
#             for child in nextLayer:
                
                
#                 if 0 <= child < len(arr) and child != node and child not in visited:
#                     visited.add(child)
#                     if child == dest:
                        
#                         return dist+1
#                     queue.append((child,dist+1))
#             del graph[arr[node]]
        
#         return -1
    
        graph = defaultdict(list)
        for i in range(len(arr)):
            graph[arr[i]].append(i)
        visited = set()
        src, dest = 0, len(arr)-1
        queue = deque()
        queue.append((src, 0))
        visited.add(src)
        while queue:
            vid, step = queue.popleft()
            if vid == dest:
                return step
            nextLayer = [vid-1, vid+1] + graph[arr[vid]]
            for v in nextLayer:
                if 0<=v<len(arr) and v!=vid and v not in visited:
                    visited.add(v)
                    queue.append((v, step+1))
            del graph[arr[vid]]
        return -1
        


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        
        # map value to list of indices
        idxs = defaultdict(list)
        for i,v in enumerate(arr):
            # don't care about v if it's sandwiched between two numbers of same value
            if (0 < i < n-1 and arr[i-1] == v == arr[i+1]):
                continue
            idxs[v].append(i)
        
        # bfs
        q = deque([(0, 0)])
        visited = set()
        while q:
            i, cnt = q.popleft()
            visited.add(i)
            
            if i == len(arr)-1:
                return cnt
            
            # left, right case
            for j in [i-1,i+1]:
                if 0 <= j < n and j not in visited:
                    q.append((j, cnt+1))
            
            # same-jump case
            for j in idxs[arr[i]]:
                if j != i and j not in visited:
                    q.append((j, cnt+1))
                    
        return -1

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        dict1={}
        i=0
        n=len(arr)
        while i<n:
            if arr[i] in dict1:
                dict1[arr[i]].append(i)
            else:
                dict1[arr[i]]=[i]
            cur=arr[i]
            j=1
            while i+j<n:
                if arr[i+j]==cur:
                    j+=1
                else:
                    break   
            if j>1:
                dict1[arr[i]].append(i+j-1)
            i+=j
        
        curPoss={0}
        cnt=0
        while curPoss!=[]:
            nextPoss=set()
            for cur in curPoss:
                if cur==n-1:
                    return cnt
                #arr[cur]=None
                l=cur-1
                if 0<l<n and l not in curPoss and arr[l]!=None:
                    nextPoss.add(l)
                r=cur+1
                if 0<r<n and r not in curPoss and arr[r]!=None:
                    nextPoss.add(r)
                #print(cur,arr[cur])
                for i in dict1[arr[cur]]:
                    if i!=cur and i not in curPoss and arr[i]!=None:
                        nextPoss.add(i)
                arr[cur]=None
            curPoss=nextPoss
            cnt+=1
            


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        queue = deque([0])
        visited = set([0])
        map = defaultdict(list)
        
        for idx, num in enumerate(arr):
            map[num].append(idx)
            
        step = 0
        
        while queue:
            size = len(queue)
            for _ in range(size):
                pos = queue.popleft()
                if pos == len(arr) - 1:
                    return step
                for nxt in [pos - 1, pos + 1]:
                    if nxt < 0 or nxt >= len(arr) or nxt in visited:
                        continue
                    queue.append(nxt)
                    visited.add(nxt)
                for neighbor in map[arr[pos]]:
                    if neighbor not in visited:
                        queue.append(neighbor)
                        visited.add(neighbor)
                #  避免TLE ,第一次已经把所有值相同的加到了queue，之后访问到和当前值相同的idx时 不需要再apply 第三条规则
                # 即for neighbor in map[arr[pos]]
                del map[arr[pos]]
            
            step += 1
        return -1


from collections import deque,defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        idxs=defaultdict(list)
        for idx,e in enumerate(arr):
            idxs[e].append(idx)
        def bfs(idx):
            q=deque([0])
            step=-1
            not_visited=set(range(len(arr)-1,0,-1))
            while q:
                step+=1
                for _ in range(len(q)):
                    node=q.popleft()
                    if node==len(arr)-1:
                        return step
                    nxt_nodes=set(idxs[arr[node]]+[node+1,node-1])
                    nxt_nodes=not_visited&nxt_nodes
                    if len(arr)-1 in nxt_nodes:
                        return step+1
                    not_visited.difference_update(nxt_nodes)
                    nxt_nodes=sorted(nxt_nodes,reverse=True)
                    q.extend(nxt_nodes)
            return -1
        return bfs(0)


class Solution:
    def minJumps(self, arr) -> int:
        n = len(arr)
        if n <= 1:
            return 0

        graph = {}
        for i in range(n):
            if arr[i] in graph:
                graph[arr[i]].append(i)
            else:
                graph[arr[i]] = [i]

        curs = [0]  # store layers from start
        visited = {0, n-1}
        step = 0

        other = [n-1] # store layers from end

        # when current layer exists
        while curs:
            # search from the side with fewer nodes
            if len(curs) > len(other):
                curs, other = other, curs
            nex = []

            # iterate the layer
            for node in curs:

                # check same value
                for child in graph[arr[node]]:
                    if child in other:
                        return step + 1
                    if child not in visited:
                        visited.add(child)
                        nex.append(child)

                # clear the list to prevent redundant search
                # graph[arr[node]].clear()

                # check neighbors
                for child in [node-1, node+1]:
                    if child in other:
                        return step + 1
                    if 0 <= child < len(arr) and child not in visited:
                        visited.add(child)
                        nex.append(child)

            curs = nex
            step += 1

        return -1


from collections import defaultdict, deque
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        node_h = defaultdict(list)
        graph = defaultdict(set)
        
        # Constructring graph based on these rules
        # i + 1 where: i + 1 < arr.length.
        # i - 1 where: i - 1 >= 0.
        # j where: arr[i] == arr[j] and i != j.
        for idx, val in enumerate(arr):
            # if idx - 1 >= 0:
            #     graph[idx].add(idx-1)
            # if idx + 1 < len(arr):
            #     graph[idx].add(idx+1)
            # for node_idx in node_h[val]:
            #     # graph[idx].add(node_idx)
            #     graph[val].add(idx)
            #     # graph[node_idx].add(idx)
            node_h[val].append(idx)

        q = deque()
        visited = set()
        q.append((0, 0))
        visited.add(0)
        
        while (q):
            node, level = q.popleft()
            if node == len(arr) - 1:
                return level
            nbrs = node_h[arr[node]]
            nbrs.append(node - 1)
            nbrs.append(node + 1)
            # for nbr in graph[node]:
            for nbr in nbrs:
                if nbr == len(arr) - 1:
                    return level + 1
                if nbr >= 0 and nbr < len(arr) and nbr not in visited:
                    q.append((nbr, level + 1))
                    visited.add(nbr)
            node_h[arr[node]] = [] # [BUG] Clearing this is crucial otherwise we might revisit the node again, causing TLE 
            
        return 0
        
# [NOTE] First attempt failed with large input of same numbers with just the last number different :)
# https://leetcode.com/submissions/detail/397710738/testcase/

# Clearing up the processed node list helped with TLE better explanation here
# https://leetcode.com/problems/jump-game-iv/discuss/502699/JavaC++-BFS-Solution-Clean-code-O(N)/445620



class Solution:
    def minJumps(self, arr: List[int]) -> int:
        from collections import defaultdict, deque
        n = len(arr)
        
        indices = defaultdict(list)
        
        for i in range(n):
            indices[arr[i]].append(i)
            
        visited = [False] * n
        visited[0] = True
        
        queue = deque()
        # add first position
        queue.append(0)
        
        steps = 0
        
        while len(queue) > 0:
            for size in range(len(queue), 0, -1):
                i = queue.popleft()
                
                # termination check
                if i == n - 1:
                    return steps
                
                next = indices[arr[i]]
                
                next.append(i - 1)
                next.append(i + 1)
                
                for num in next:
                    if num >= 0 and num < n and not visited[num]:
                        visited[num] = True
                        queue.append(num)
                        
                # remove already looked up indices
                indices[arr[i]] = []
                
            steps += 1
            
        return 0

from collections import defaultdict, deque
class Solution:
    def minJumps(self, arr):
        n = len(arr)
        if n == 1: return 0
        d = defaultdict(list)
        for i,val in enumerate(arr):
            d[val].append(i)
            
        visited = set([0])
        stack = deque([0])
        k, jumps = len(stack), 1
        while stack:
            k -= 1
            i = stack.popleft()
            childs = [j for j in d.pop(arr[i],[])]
            for j in [i-1,i+1]:
                if 0 <= j < n and arr[j] != arr[i] and j not in visited: childs.append(j)
            visited |= set(childs)
            if n-1 in visited: return jumps
            stack += childs
            if not k:
                k = len(stack)
                jumps += 1
        return jumps

from collections import deque, defaultdict

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        visited = {0}
        q = deque([(0, 0)])
        val_to_is = defaultdict(list)
        
        for i, val in enumerate(arr):
            val_to_is[val].append(i)
        
        def move(i):
            for j in [i - 1, i + 1] + val_to_is[arr[i]]:
                if 0 <= j < len(arr) and j != i and j not in visited:
                    yield j
                    
        while q:
            i, steps = q.pop()
            for j in move(i):
                if j == len(arr) - 1:
                    return steps + 1
                visited.add(j)
                if arr[i] in val_to_is:
                    del val_to_is[arr[i]]
                q.appendleft((j, steps + 1))
        
        return 0


class Solution:
    def minJumps(self, arr):
        # Similar concept to jump game3, but here we need to find the minimum
        # jumps so we need to use queue instead of stack, also we need to use
        # hashmap to handle the third jump of mirror values
        
        # Base Case - No jumps needed
        if len(arr) == 1:
            return 0
        
        # Data Structure Declaration
        q = collections.deque()
        seen = set()
        hashmap = collections.defaultdict(list)
        destination = len(arr)-1
        minJumps = 0
        
        # Store mirrors in hashmap
        for index, num in enumerate(arr):
            hashmap[num].append(index)
        

        # Traversal start points
        q.append(0)
        seen.add(0)

        # Run loop until we have values in queue
        while q:
            
            sizeQ = len(q)
            
            # Traverse the queue level by level
            for i in range(sizeQ):
                Pos = q.popleft()
                # Check for destination
                if Pos == destination:
                    return minJumps
                
                # Number of choices for Jumping
                nextPos = Pos + 1
                prevPos = Pos - 1
                mirrorPos = hashmap[arr[Pos]]
                
                # Add if nextPos is valid
                if nextPos >= 0 and nextPos < len(arr) and nextPos not in seen:
                    seen.add(nextPos)
                    q.append(nextPos)
                    
                # Add if prevPos is valid
                if prevPos >= 0 and prevPos < len(arr) and prevPos not in seen:
                    seen.add(prevPos)
                    q.append(prevPos)
                
                # Add if we have mirror elements present
                if mirrorPos:
                    for val in mirrorPos:
                        if val >= 0 and val < len(arr) and val not in seen:
                            seen.add(val)
                            q.append(val)
                    # Once current element is taken into account, delete from map
                    del hashmap[arr[Pos]]
            # for every level increase the number of Jumps
            minJumps += 1
        return minJumps
                


class Solution:
    # bidirectional, 460 ms
    def minJumps(self, arr):
        if len(arr) == 1: return 0
        if arr[0] == arr[-1]: return 1

        length = len(arr)
        if len(set(arr)) == length: return length - 1
        _map = defaultdict(set) # connection map
        for i, val in enumerate(arr): _map[val].add(i)

        # bfs, seen: visited index, visit: visited connextion
        res, visit = 0, set()
        seen = {0}
        curs, other = {0}, {length - 1}
        while curs:
            res += 1
            thisLevel = set() # indexes can be seen in this level
            for i in curs:
                if i - 1 > 0 and i - 1 not in seen: 
                    thisLevel.add(i - 1)
                if arr[i] not in visit:
                    thisLevel |= (_map[arr[i]] - seen) 
                    visit.add(arr[i])
                if i + 1 < length and i + 1 not in seen: 
                    thisLevel.add(i + 1)
            if len(thisLevel & other) > 0: return res               
            curs = thisLevel
            if len(curs) > len(other): curs, other = other, curs
            else: seen |= thisLevel

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        nei = collections.defaultdict(list)
        _ = [nei[x].append(i) for i, x in enumerate(arr)]

        frontier = collections.deque([(0,0)])
        num_met, pos_met = set(), set()
        while frontier:
            pos, step = frontier.popleft() # state: position, step
            if pos == len(arr) - 1: return step
            num = arr[pos]
            pos_met.add(pos) # track explored positions

            for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
                if p in pos_met or not 0 <= p < len(arr): continue
                frontier.append((p, step + 1))

            num_met.add(num) # track explored values

from queue import Queue
def dedup(arr):
    n = len(arr)
    if n <= 2:
        return arr
    
    ret = [arr[0]]
    is_equal = False
    for i in range(1, n):
        if arr[i] == arr[i-1]:
            if not is_equal:
                is_equal = True
                ret.append(arr[i])
            else:
                #visited[ret[-1]] = 1
                ret[-1] = arr[i]                
        else:
            ret.append(arr[i])
            is_equal = False
    return ret     
        
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(set(arr)) == len(arr):
            return len(arr)-1
        
        arr = dedup(arr)
        memo = defaultdict(list)
        n = len(arr)
        visited = [0] *n
        for i in range(n):
            memo[arr[i]].append(i)
        
        #for k in memo.keys():
        #    memo[k] = dedup(memo[k], visited)
            
        q = Queue()
        q.put((0,0))
        visited[0] = 1
        while not q.empty():
            cur, cnt = q.get()
            if cur == n - 1:
                return cnt
                
            wk = [cur+1, cur-1]
            for v in memo[arr[cur]]+wk:
                #print(cur, v)
                if -1 < v < n and not visited[v]:
                    q.put((v,cnt+1))
                    visited[v] = 1
        return 0

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        dp = {}
        count = {}
        for i in range(len(arr)):
            res = count.get(arr[i], [])
            res.append(i)
            count[arr[i]] = res
        
        vis = set()
        vis.add(0)
        q = collections.deque([(0, 0)])
        c = 0
        while q:
            l = len(q)
            for i in range(l):
                node = q.popleft()
                if node[0] == len(arr) - 1:
                    return node[1]
            
                if node[0] != 0:
                    if node[0] - 1 not in vis:
                        q.append((node[0] - 1, node[1] + 1))
                        vis.add(node[0] - 1)
            
                if node[0] != len(arr) - 1:
                    if node[0] + 1 not in vis:
                        q.append((node[0] + 1, node[1] + 1))
                        vis.add(node[0] + 1)
                
                for j in count[arr[node[0]]]:
                    if j not in vis and j != node[0]:
                        q.append((j, node[1] + 1))
                        vis.add(j)
                if j in count[arr[node[0]]]:
                    count[arr[node[0]]] = []
                    
            c += 1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        indexes = collections.defaultdict(list)
        for idx, v in enumerate(arr):
            indexes[v].append(idx)
        #early pruning.
        for key in indexes:
            indexes[key] = [
                v
                for j, v in enumerate(indexes[key]) 
                if not (
                    1 <= j < len(indexes[key]) - 1 
                    and indexes[key][j-1]==v-1 
                    and indexes[key][j+1]==v+1
                )
            ]
        
        queue, visited = collections.deque([(0, 0)]), set([0])
        
        while queue:
            idx, jumps = queue.popleft()
            if idx == len(arr) - 1:
                return jumps
            
            v = arr[idx]
            for j in [idx + 1, idx - 1] + indexes[v][::-1]:
                if 0 <= j < len(arr) and j not in visited:
                    visited.add(j)
                    queue.append((j, jumps + 1))
                    
# class Solution:
#     def minJumps(self, arr: List[int]) -> int:
#         a_i = collections.defaultdict(list)
#         for i, a in enumerate(arr):
#             a_i[a].append(i)
#         def bfs():
#             from collections import deque
#             Q = deque([(0,0)])
#             seen = {0}
#             while Q:
#                 i, d = Q.popleft()
#                 if i==len(arr)-1:return d
#                 for j in [i-1, i+1]+a_i[arr[i]][::-1]:
#                     if 0<=j<len(arr) and j!=i and j not in seen:
#                         seen.add(j)
#                         if j==len(arr)-1:return d+1
#                         Q.append((j,d+1))
#         return bfs()


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        map = defaultdict(list)
        for i, item in enumerate(arr):
            map[item].append(i)
        
        q = deque()
        q.appendleft((0, 0))
        visited = set()
        num_vis = set()
        while q:
            index, jumps = q.pop()
            if index == len(arr)-1: return jumps
            visited.add(index)
            if arr[index] not in num_vis:
                nxts = map[arr[index]]
                num_vis.add(arr[index])
            
                for nxt in nxts:
                    if nxt<0 or nxt>len(arr) or nxt in visited: continue
                    q.appendleft((nxt, jumps+1))
            
            for nbr in [index+1, index-1]:
                if nbr<0 or nbr>=len(arr) or nbr in visited: continue
                q.appendleft((nbr, jumps+1))

        return -1


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if not arr or len(arr) == 1:
            return 0
        
        n = len(arr)
        
        same_val = {}
        for i in range(n):
            if arr[i] not in same_val:
                same_val[arr[i]] = [i]
            else:
                same_val[arr[i]].append(i)
                
        visited = [False] * n
        step = 0
        curr = [0]
        
        while curr:
            next = []
            
            for i in curr:
                if i == n-1: # reached end
                    return step
                
                visited[i] = True
                
                for next_idx in same_val[arr[i]]:
                    if not visited[next_idx]:
                        next.append(next_idx)
                        
                same_val[arr[i]].clear() # critical step: clear the same_val list to prevent redundant search!
                
                for next_idx in [i-1, i+1]:
                    if 0 <= next_idx < n and not visited[next_idx]:
                        next.append(next_idx)
                        
            curr = next
            step += 1
            
        return -1 # unreachable

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # BFS next step: +1, -1, same val pos
        # val_to_pos dict
        # dist dict
        
        if not arr:
            return 0
        
        
        
        n = len(arr)
        
        val_to_pos = collections.defaultdict(list)
        
        for i, val in enumerate(arr):
            val_to_pos[val].append(i)
        
        dist = 0
        
        curr_set = set([0])
        other_set = set([n - 1])
        
        curr_visited = curr_set
        other_visited = other_set
        
        while curr_set and other_set:
            if len(other_set) < len(curr_set):
                curr_set, other_set = other_set, curr_set
                curr_visited, other_visited = other_visited, curr_visited
            
            next_set = set()
            
            while curr_set:
                curr = curr_set.pop()
                
                
                if curr in other_visited:
                    return dist
                
                for nei in val_to_pos[arr[curr]] + [curr + 1, curr - 1]:
                    if not 0 <= nei < n:
                        continue
                    
                    if nei in curr_visited:
                        continue
                    
                    
                    next_set.add(nei)
                
                val_to_pos[arr[curr]] = []
                
                
            curr_visited |= next_set
            curr_set = next_set
            dist += 1
        


#20201003 链表
class Solution:
    def minJumps(self, arr):
        length = len(arr)
        if len(set(arr)) == length: return length - 1
        if arr[0] == arr[-1]: return 1

        _map = defaultdict(set) # connection map
        for i, val in enumerate(arr): _map[val].add(i)

        res, seen, visit = 0, {0}, set()
        curs, other = {0}, {length - 1}
        while curs:
            res += 1

            thisLevel = set()
            for i in curs:
                if i - 1 > 0 and i - 1 not in seen: 
                    thisLevel.add(i - 1)
                if arr[i] in _map:
                    thisLevel |= (_map[arr[i]] - seen) 
                    visit.add(arr[i])
                    del _map[arr[i]]
                if i + 1 < length and i + 1 not in seen: 
                    thisLevel.add(i + 1)

            if thisLevel & other: return res          
            curs = thisLevel
            if len(curs) > len(other): curs, other = other, curs
            else: seen |= thisLevel

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1: return 0
        dictor = collections.defaultdict(list)
        queue = collections.deque([(0, 0)])
        
        for i in range(n):
            dictor[arr[i]].append(i)
        
        
        seen = set([0, n-1])
        while queue:
            idx, step = queue.popleft()
            indexes = dictor[arr[idx]]
            for i in indexes:
                if i == n - 1:
                    return step + 1
                if i not in seen:
                    queue.append((i, step + 1))
                    seen.add(i)
            del dictor[arr[idx]]
            
            for di in [-1, 1]:
                new_i = idx + di
                if new_i == n - 1:
                    return step + 1
                if 0 <= new_i < len(arr) and new_i not in seen:
                    queue.append((new_i, step + 1))
                    seen.add(new_i)
        return -1
                    


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        g = defaultdict(list)
        for i, v in enumerate(arr):
            g[v].append(i)
        N = len(arr)
        
        val_flag = set()
        
        cost = [math.inf] * N
        cost[0] = 0
        heap = [(0, 0)]
        
        while heap:
            c, i = heappop(heap)
            # print(f'Now {i}  Cost {c}  Heap {heap}')
            if i == N-1:
                return c
            for n in (g[arr[i]] * (arr[i] not in val_flag)) + [i-1, i+1]:
                if not 0 <= n < N:
                    continue
                if cost[n] > c + 1:
                    cost[n] = c + 1
                    heappush(heap, (c+1, n))
            
            val_flag.add(arr[i])
        return cost[-1]

from collections import deque,defaultdict
class Solution:
    def minJumps(self, arr: List[int]) -> int:
        idxs=defaultdict(set)
        for idx,e in enumerate(arr):
            idxs[e].add(idx)
        def bfs(idx):
            q=deque([0])
            step=-1
            not_visited=set(range(len(arr)-1,0,-1))
            while q:
                step+=1
                for _ in range(len(q)):
                    node=q.popleft()
                    if node==len(arr)-1:
                        return step
                    nxt_nodes=idxs[arr[node]]
                    nxt_nodes=not_visited&nxt_nodes
                    for nxt in [node-1,node+1]:
                        if nxt in not_visited:
                            nxt_nodes.add(nxt)
                    if len(arr)-1 in nxt_nodes:
                        return step+1
                    not_visited.difference_update(nxt_nodes)
                    nxt_nodes=nxt_nodes
                    q.extend(nxt_nodes)
            return -1
        bfs(0)
        return bfs(0)


class Solution:
    def minJumps(self, arr):
        nei = collections.defaultdict(list)
        _ = [nei[x].append(i) for i, x in enumerate(arr)]

        frontier = collections.deque([(0,0)])
        num_met, pos_met = set(), set()
        while frontier:
            pos, step = frontier.popleft() # state: position, step
            if pos == len(arr) - 1: return step
            num = arr[pos]
            pos_met.add(pos) # track explored positions

            for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
                if p in pos_met or not 0 <= p < len(arr): continue
                frontier.append((p, step + 1))

            num_met.add(num) # track explored values

class Solution:
  def minJumps(self, arr):
    nei = collections.defaultdict(list)
    _ = [nei[x].append(i) for i, x in enumerate(arr)]

    frontier = collections.deque([(0,0)])
    num_met, pos_met = set(), set()
    while frontier:
        pos, step = frontier.popleft() # state: position, step
        if pos == len(arr) - 1: return step
        num = arr[pos]
        pos_met.add(pos) # track explored positions

        for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
            if p in pos_met or not 0 <= p < len(arr): continue
            frontier.append((p, step + 1))

        num_met.add(num) # track explored values

class Solution:
    def minJumps(self, arr):
        nei = collections.defaultdict(list)
        _ = [nei[x].append(i) for i, x in enumerate(arr)]

        frontier = collections.deque([(0,0)])
        num_met, pos_met = set(), set()
        while frontier:
            pos, step = frontier.popleft() # state: position, step
            if pos == len(arr) - 1: return step
            num = arr[pos]
            pos_met.add(pos) # track explored positions

            for p in [pos - 1, pos + 1] + nei[num] * (num not in num_met):
                if p in pos_met or not 0 <= p < len(arr): continue
                frontier.append((p, step + 1))

            num_met.add(num) # track explored values


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        pos = {}
        for i, x in enumerate(arr):
            if x in pos:
                pos[x][0].append(i)
            else:
                pos[x] = [[i], False]
            
        q = deque([(len(arr) - 1, 0, True), (0, 0, False)])
        visited = [[-1,-1] for _ in range(len(arr))]
        
        while q:
            i, n, d = q.popleft()
            
            if visited[i][int(not d)] != -1:
                return n + visited[i][int(not d)]
            
            if visited[i][int(d)] != -1:
                continue
            visited[i][int(d)] = n
            
            if i < len(arr) - 1:
                q.append((i+1, n+1, d))
            if i > 0:
                q.append((i-1, n+1, d))
            
            if not pos[arr[i]][1]:
                for idx in pos[arr[i]][0]:
                    q.append((idx, n+1, d))
                pos[arr[i]][1] = True