https://leetcode.com/problems/jump-game-iv

In this problem we are asked to find shortest path between two nodes in some graph, so the first idea you should think is bfs (or Dijkstra algorithm). Actually, bfs is almost sufficient here, but we need to do one optimization which increase our speed dramatically.

  1. Let us use d: defaultdict, where for each value we keep list of all possible indexes for this value. We need this to make fast steps of type 3.
  2. Let visited be as usual set of visited nodes, we need it in usual bfs, not to visit any node two times.
  3. Let visited_groups be set of visited values: we need it for the following reason. Imagine, we have arr = [1, 1, 1, 1, 1, 1, 1, 1, 1, 2]. Then first time we see 1, we visit all other 1. Second time we see 1, we do not need to check its neibors of type 3, we already know that we visited them. Without this optimization time complexity can be potentially O(n^2).
  4. What we do next is classical bfs: we extract node from queue, visit two neibors of types 1 and 2 and if we did not visit value of this node yet, we visit its all neibors of type 3.

Complexity: time complexity is O(n): we visit every index only once and try to visit every node no more than 3 times: for each type of neighbors. Space complexity is O(n) as well: to keep visited and visited_groups sets.

class Solution:
    def minJumps(self, arr):
        n = len(arr)
        d = defaultdict(list)
        for i, num in enumerate(arr):
            d[num].append(i)
            
        queue = deque([(0, 0)])
        visited, visited_groups = set(), set()
        
        while queue:
            steps, index = queue.popleft()
            if index == n - 1: return steps
            
            for neib in [index - 1, index + 1]:
                if 0 <= neib < n and neib not in visited:
                    visited.add(neib)
                    queue.append((steps + 1, neib))
            
            if arr[index] not in visited_groups:
                for neib in d[arr[index]]:
                    if neib not in visited:
                        visited.add(neib)
                        queue.append((steps + 1, neib))
                visited_groups.add(arr[index])

If you like the solution, you can upvote it on leetcode discussion section: Problem 1345