Jump Game IV — Hard Problem & Solution

You start at index 0 of an array. From index i you may jump to i + 1, to i - 1, or to any index j with arr[i] == arr[j], as long as the destination is…

Difficulty: Hard
Topics: Arrays, Hash Table, Breadth-First Search
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You start at index 0 of an array. From index i you may jump to i + 1, to i - 1, or to any index j with arr[i] == arr[j], as long as the destination is inside the array.

Return the minimum number of jumps needed to reach the last index.

Example 1

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: Jump 0 → 4 (both 100), then 4 → 3, then 3 → 9 (both 404).

Example 2

Input: arr = [7]
Output: 0
Explanation: You already are at the last index.

Example 3

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: Jump straight from the first 7 to the last.

Constraints

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

How to solve Jump Game IV

Model indices as nodes and jumps as unit edges, then BFS. Grouping indices by value gives the value-jumps cheaply, and clearing each group after it is expanded keeps the whole search linear.

Approach

Bucket the indices by their value.
BFS from index 0. When popping u, enqueue every unvisited index in arr[u]'s bucket, then delete the bucket.
Also enqueue u - 1 and u + 1 if they are in range and unvisited.
Return the distance when the last index is popped.

Why it works

Clearing the bucket is what stops the algorithm from being quadratic: a value shared by 50 000 indices would otherwise be scanned once per member. It is safe because the first time the group is expanded every member gets its final (minimum) distance, so a later visit could never improve anything — the group's whole usefulness is spent in one go.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Without clearing the buckets a long run of equal values is O(n²) and times out.
A single-element array answers 0.
Mark visited on enqueue; marking on dequeue lets duplicates pile up.

Reference solution

Python

from typing import List
from collections import defaultdict, deque

def minJumps(arr: List[int]) -> int:
    n = len(arr)
    if n <= 1:
        return 0
    by_val = defaultdict(list)
    for i, v in enumerate(arr):
        by_val[v].append(i)
    dist = [-1] * n
    dist[0] = 0
    q = deque([0])
    while q:
        u = q.popleft()
        if u == n - 1:
            return dist[u]
        if arr[u] in by_val:
            for v in by_val[arr[u]]:
                if dist[v] < 0:
                    dist[v] = dist[u] + 1
                    q.append(v)
            del by_val[arr[u]]
        for v in (u - 1, u + 1):
            if 0 <= v < n and dist[v] < 0:
                dist[v] = dist[u] + 1
                q.append(v)
    return -1

JavaScript

var minJumps = function(arr) {
    var n = arr.length, i;
    if (n <= 1) return 0;
    var byVal = new Map();
    for (i = 0; i < n; i++) {
        var list = byVal.get(arr[i]);
        if (list) list.push(i);
        else byVal.set(arr[i], [i]);
    }
    var dist = [];
    for (i = 0; i < n; i++) dist.push(-1);
    dist[0] = 0;
    var q = [0];
    var head = 0;
    while (head < q.length) {
        var u = q[head++];
        if (u === n - 1) return dist[u];
        var bucket = byVal.get(arr[u]);
        if (bucket) {
            for (i = 0; i < bucket.length; i++) {
                var v = bucket[i];
                if (dist[v] >= 0) continue;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
            byVal["delete"](arr[u]);
        }
        if (u - 1 >= 0 && dist[u - 1] < 0) { dist[u - 1] = dist[u] + 1; q.push(u - 1); }
        if (u + 1 < n && dist[u + 1] < 0) { dist[u + 1] = dist[u] + 1; q.push(u + 1); }
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue