Jumps Game

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.

Notice that you can not jump outside of the array at any time.

Example 1:

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.

BFS Solution

BFS seems like a straghtforward way to do it since we are searching for the shortest way in the graph. We will require: - a function that pickes next steps based on the roles (back, forward, jump) - for picking where to jump we will use a mapping from values into their positions int -> [int] - a simple que of next steps - in order to avoid cycles we need another hash of visited positions we will also use it to retrace our steps

from typing import List, Dict, Set, Deque
from collections import deque


class Solution:

    m: Dict[int, List[int]]
    q: Deque[int]
    distances: Dict[int, int]
    arr: List[int]

    def __init__(self):
        self.m = dict()
        self.q = deque()
        self.distances = dict()

    def minJumps(self, arr: List[int]) -> int:
        # edge cases
        if len(arr) < 3:
            return len(arr) - 1
        self.arr = arr
        self.buildM()
        result = self.pickNext(0)
        while len(self.q) > 0:
            if result is not None:
                break
            position = self.q.popleft()
            result = self.pickNext(position)
        return result if result is not None else 0

    def compressInput(self, arr: List[int]) -> List[int]:
        result = [arr[0]]
        for i in range(1, len(arr)-1):
            if arr[i] != arr[i-1] or arr[i] != arr[i+1]:
                result.append(arr[i])
        result.append(arr[-1])
        return result

    def buildM(self):
        for (i, x) in enumerate(self.arr):
            ml = self.m.setdefault(x, [])
            ml.append(i)

    def pickNext(self, pos: int) -> None | int:

        ml = reversed(self.m.get(self.arr[pos], []))
        self.m[self.arr[pos]] = []
        distance = self.distances.get(pos,0)

        nearest = []
        if pos < len(self.arr) - 1:
            nearest.append(pos + 1)
        if pos > 0:
            nearest.append(pos - 1)

        for t in [ml, nearest]:
            for p in t:
                if p not in self.distances:
                    if p >= len(self.arr) - 1:
                        return distance + len(self.arr) - p 
                    self.q.append(p)
                    self.distances[p] = distance + 1

Artem Putilov, 2023