Leetcode: 1345. Jump Game IV

Mistake: Bug caused by debug code.
Can we formulate the problem using graphs? Each element of the array is a vertex and edges are created following the rules. The problem becomes finding the Shortest Path in a Graph Problem which can be done by a Breadth-first search since edges have no weight. Time and space complexity is \(O(n)\).

from typing import List


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

        N = len(arr)
        vis = [False] * N

        queue = [(0, 0)]
        vis[0] = True

        for (steps, i) in queue:
            if i == N - 1:
                return steps
            while adj[arr[i]]:
                j = adj[arr[i]].pop()
                if not vis[j]:
                    vis[j] = True
                    queue.append((steps + 1, j))
            for j in i + 1, i - 1:
                if 0 <= j < N and not vis[j]:
                    vis[j] = True
                    queue.append((steps + 1, j))


assert Solution().minJumps([100, -23, -23, 404, 100, 23, 23, 23, 3, 404]) == 3
assert Solution().minJumps([7]) == 0
assert Solution().minJumps([7, 6, 9, 6, 9, 6, 9, 7]) == 1