Jump Game IV — LeetCode 1345 Python Solution

The problem

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.

Example

Input

arr = [100,-23,-23,404,100,23,23,23,3,404]

Output

3

Explanation

You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Python solution

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        g = defaultdict(list)
        for i, x in enumerate(arr):
            g[x].append(i)
        q = deque([0])
        vis = {0}
        ans = 0
        while 1:
            for _ in range(len(q)):
                i = q.popleft()
                if i == len(arr) - 1:
                    return ans
                for j in (i + 1, i - 1, *g.pop(arr[i], [])):
                    if 0 <= j < len(arr) and j not in vis:
                        q.append(j)
                        vis.add(j)
            ans += 1

Complexity

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1345. Jump Game IV is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Related problems