Jump Game IV

hard bfs hash map

Problem

Given an array arr, you start at index 0. From index i you may jump to i+1, i-1, or any index j where arr[i] == arr[j]. Return the minimum number of jumps to reach the last index.

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

Output3

0 → 4 (same 100) → 3 (i-1) → 9 (same 404). 3 jumps.

arr (comma-separated)

from collections import deque, defaultdict

def min_jumps(arr):
    n = len(arr)
    if n == 1: return 0
    groups = defaultdict(list)
    for i, v in enumerate(arr): groups[v].append(i)
    visited = {0}
    q = deque([(0, 0)])
    while q:
        i, d = q.popleft()
        for j in (i - 1, i + 1):
            if 0 <= j < n and j not in visited:
                if j == n - 1: return d + 1
                visited.add(j); q.append((j, d + 1))
        if arr[i] in groups:
            for j in groups[arr[i]]:
                if j not in visited:
                    if j == n - 1: return d + 1
                    visited.add(j); q.append((j, d + 1))
            del groups[arr[i]]
    return -1

function minJumps(arr) {
  const n = arr.length;
  if (n === 1) return 0;
  const groups = new Map();
  for (let i = 0; i < n; i++) {
    if (!groups.has(arr[i])) groups.set(arr[i], []);
    groups.get(arr[i]).push(i);
  }
  const visited = new Set([0]);
  const q = [[0, 0]];
  while (q.length) {
    const [i, d] = q.shift();
    for (const j of [i - 1, i + 1]) {
      if (j >= 0 && j < n && !visited.has(j)) {
        if (j === n - 1) return d + 1;
        visited.add(j); q.push([j, d + 1]);
      }
    }
    if (groups.has(arr[i])) {
      for (const j of groups.get(arr[i])) {
        if (!visited.has(j)) {
          if (j === n - 1) return d + 1;
          visited.add(j); q.push([j, d + 1]);
        }
      }
      groups.delete(arr[i]);
    }
  }
  return -1;
}

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], k -> new ArrayList<>()).add(i);
        boolean[] visited = new boolean[n]; visited[0] = true;
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int i = cur[0], d = cur[1];
            for (int j : new int[]{i - 1, i + 1}) {
                if (j >= 0 && j < n && !visited[j]) {
                    if (j == n - 1) return d + 1;
                    visited[j] = true; q.offer(new int[]{j, d + 1});
                }
            }
            if (groups.containsKey(arr[i])) {
                for (int j : groups.get(arr[i])) {
                    if (!visited[j]) {
                        if (j == n - 1) return d + 1;
                        visited[j] = true; q.offer(new int[]{j, d + 1});
                    }
                }
                groups.remove(arr[i]);
            }
        }
        return -1;
    }
}

int minJumps(vector<int>& arr) {
    int n = arr.size();
    if (n == 1) return 0;
    unordered_map<int, vector<int>> groups;
    for (int i = 0; i < n; i++) groups[arr[i]].push_back(i);
    vector<bool> visited(n, false); visited[0] = true;
    queue<pair<int,int>> q; q.push({0, 0});
    while (!q.empty()) {
        auto [i, d] = q.front(); q.pop();
        for (int j : {i - 1, i + 1}) {
            if (j >= 0 && j < n && !visited[j]) {
                if (j == n - 1) return d + 1;
                visited[j] = true; q.push({j, d + 1});
            }
        }
        if (groups.count(arr[i])) {
            for (int j : groups[arr[i]]) {
                if (!visited[j]) {
                    if (j == n - 1) return d + 1;
                    visited[j] = true; q.push({j, d + 1});
                }
            }
            groups.erase(arr[i]);
        }
    }
    return -1;
}

Explanation

We want the fewest jumps from index 0 to the last index, where from i you can step to i+1, i-1, or any index with the same value. "Fewest steps" on an unweighted graph screams BFS — the first time we reach the end, that's the minimum.

We pre-group indices by value into groups (a hash map from value to the list of indices holding it). That lets a same-value jump reach all matching indices in one shot, instead of scanning the array each time.

BFS then processes indices level by level, where each level is one more jump. For the current index i at distance d, we enqueue the unvisited neighbors i-1 and i+1 plus every index in groups[arr[i]], each at distance d + 1.

The crucial optimization: after expanding a value's group once, we delete it from groups. Without this, large blocks of equal values would be re-scanned over and over, breaking the linear time bound. Once cleared, the group never needs visiting again.

Example: arr = [100,-23,-23,404,100,23,23,23,3,404]. BFS finds 0 → 4 (same 100) → 3 (step) → 9 (same 404), reaching the last index in 3 jumps.

Time: O(n) Space: O(n)