Problem Statement in English

You are 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.

Approach

This problem can be solved using a breadth-first search (BFS) approach. We can treat the array as a graph where each index is a node and there are edges between nodes that can be reached in one step.

We will use a queue to perform the BFS and a set to keep track of visited nodes to avoid cycles.

Since we can also jump to any index with the same value, we can maintain a dictionary that maps each value to the list of indices where that value occurs. This will allow us to quickly find all the indices we can jump to for a given value.

After we’ve processed all the jumps for a particular value, we can remove that value from the dictionary to avoid redundant checks in the future.

And we’re done!

Solution in Python


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

        jumps = defaultdict(list)

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

        q = deque([(0, 0)])
        seen = {0}

        while q:
            steps, node = q.popleft() 
            options = []

            for j in jumps[arr[node]]:
                if j in seen: continue

                if j == n - 1: return steps + 1
                seen.add(j)
                q.append((steps + 1, j))

            for delta in [+1, -1]:
                nnode = node + delta
                if nnode < 0 or nnode >= n: continue
                if nnode in seen: continue

                if nnode == n - 1: return steps + 1
                seen.add(nnode)
                q.append((steps + 1, nnode))

            del jumps[arr[node]]

        return n

Complexity

  • Time: $O(n)$
    Since we visit each node at most once and also visit each jump at most once.

  • Space: $O(n)$
    Since we store the jumps in a dictionary and also maintain a queue and a seen set.

Mistakes I Made

I was using Dijkstra’s algorithm instead of BFS. Dijkstra’s algorithm is not needed here since all edges have the same weight (1). BFS is sufficient to find the shortest path in an unweighted graph.

And we are done.