1345. Jump Game IV

Array
Hash Table
BFS

TIME

O(n)

SPACE

O(n)

Intuition

Treat every index as a node in an unweighted graph. From an index, we can move to the adjacent indices and to every other index with the same value.

Since every jump has the same cost, BFS gives the minimum number of steps.

The main issue is avoiding repeated scans of all indices with the same value. Once BFS expands the teleport edges for a value, those edges never need to be considered again because any later visit would be at the same or a larger distance.

Approach

Build a map from each value to all indices containing that value.
Start BFS from index 0.
For each popped index:
- return the current step count if it is the last index
- try index - 1 and index + 1
- try every index with the same value
After processing same-value jumps for arr[index], clear that value's list from the map.
Mark indices as visited before enqueueing them.

Complexity

Time: O(n), each index is enqueued once, and each same-value group is expanded once
Space: O(n), for the value map, queue, and visited array

Edge Cases

Single element array -> return 0
First and last elements are equal -> return 1
Many duplicate values -> handled efficiently by clearing each value group
Negative values -> supported as normal hash map keys

Code

from collections import defaultdict, deque
from typing import List


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        """
        1345. Jump Game IV
        Time: O(n)
        Space: O(n)
        """
        n = len(arr)
        if n == 1:
            return 0

        value_to_indices = defaultdict(list)
        for index, value in enumerate(arr):
            value_to_indices[value].append(index)

        visited = [False] * n
        visited[0] = True
        queue = deque([0])
        steps = 0

        while queue:
            for _ in range(len(queue)):
                index = queue.popleft()

                if index == n - 1:
                    return steps

                next_indices = value_to_indices[arr[index]]
                next_indices.append(index - 1)
                next_indices.append(index + 1)

                for next_index in next_indices:
                    if 0 <= next_index < n and not visited[next_index]:
                        visited[next_index] = True
                        queue.append(next_index)

                value_to_indices[arr[index]].clear()

            steps += 1

        return -1

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 1345. Jump Game IV
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 0;
        }

        Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
        for (int index = 0; index < n; index++) {
            valueToIndices.computeIfAbsent(arr[index], key -> new ArrayList<>()).add(index);
        }

        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        visited[0] = true;

        int steps = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int count = 0; count < levelSize; count++) {
                int index = queue.poll();
                if (index == n - 1) {
                    return steps;
                }

                List<Integer> nextIndices = valueToIndices.get(arr[index]);
                nextIndices.add(index - 1);
                nextIndices.add(index + 1);

                for (int nextIndex : nextIndices) {
                    if (nextIndex >= 0 && nextIndex < n && !visited[nextIndex]) {
                        visited[nextIndex] = true;
                        queue.offer(nextIndex);
                    }
                }

                nextIndices.clear();
            }

            steps++;
        }

        return -1;
    }
}