339. Jump Game IV

This is a shortest-path (fewest steps) problem, so BFS. From i you can step to i-1, i+1, or teleport to any index sharing arr[i]'s value. Group indices by value up front; after using a value group once, clear it so the whole group is never scanned again — that keeps BFS linear.

Shortest steps → BFS

Every move costs one step, so the minimum number of steps to the last index is a breadth-first search from index 0.

Neighbors

From index i you can go to:

• i - 1 and i + 1 (in bounds), and
• any j with arr[j] == arr[i] (a "teleport" to an equal value).

Precompute a map value -> list of indices. The catch: a value shared by many indices could be scanned repeatedly and blow up to O(n^2). The fix — after expanding a value group once, clear that group's list. Every index still gets teleported to at most once, so total work stays O(n).

The BFS

dist[0] = 0; queue = [0]
while queue:
    i = pop
    if i == n-1: return dist[i]
    for j in (i-1, i+1) + groups[arr[i]]:
        if 0 <= j < n and j unseen: dist[j] = dist[i]+1; push j
    groups[arr[i]] = []      # never expand this value again

Worked example

arr = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404] (length 10, target index 9).

• Step 1 from index 0: neighbors 1 and the other 100 at index 4.
• Step 2 from index 4: neighbors include index 3 (404).
• Step 3 from index 3: teleport to the other 404 at index 9 — the target.

Minimum steps = 3.

Complexity

• Time: O(n) — each index and each value group is expanded once.
• Space: O(n) for the map, queue, and distances.

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n == 1) return 0;
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            groups.computeIfAbsent(arr[i], z -> new ArrayList<>()).add(i);
        }
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[0] = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int i = queue.poll();
            if (i == n - 1) return dist[i];
            List<Integer> group = groups.getOrDefault(arr[i], new ArrayList<>());
            group.add(i + 1);
            group.add(i - 1);
            for (int j : group) {
                if (j >= 0 && j < n && dist[j] == -1) {
                    dist[j] = dist[i] + 1;
                    queue.offer(j);
                }
            }
            group.clear();  // never expand this value group again
        }
        return -1;
    }
}