1345.md

1345. Jump Game IV

Solution 1 (time O(n), space O(n))

class Solution(object):
    def minJumps(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        d = collections.defaultdict(list)
        for i, v in enumerate(arr):
            d[v].append(i)
        vis = set([0])
        q = deque()
        q.append((0, 0))
        while q:
            idx, step = q.popleft()
            if idx == len(arr) - 1:
                return step
            step += 1
            for new_idx in d[arr[idx]]:
                if new_idx not in vis:
                    vis.add(new_idx)
                    q.append([new_idx, step])
            del d[arr[idx]]
            if idx + 1 < len(arr) and idx + 1 not in vis:
                vis.add(idx + 1)
                q.append([idx + 1, step])
            if idx - 1 >= 0 and idx - 1 not in vis:
                vis.add(idx - 1)
                q.append([idx - 1, step])
        return -1