1345. Jump Game IV (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def minJumps(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        h = {}
        n = len(arr)
        if n <= 1:
            return 0
        for i in range(n):
            if arr[i] in h:
                h[arr[i]].append(i)
            else:
                h[arr[i]] = [i]
                
        # # slower
        # for i, num in enumerate(arr):
        #     h[num] = h.get(num, []) + [i]
        
        seen = {0}
        queue = [0]
        result = 0
        while queue:
            level = []
            for i in queue:
                if i == n - 1:
                    return result
                for j in h[arr[i]]:
                    if j not in seen:
                        level.append(j)
                        seen.add(j)
                h[arr[i]] = []
                if i > 0 and i - 1 not in seen:
                    level.append(i - 1)
                    seen.add(i - 1)
                if i < n - 1 and i + 1 not in seen:
                    level.append(i + 1)
                    seen.add(i + 1)
            result += 1 
            queue = level
        return result