Jump Game IV

Hard
940.

Jump Game IV

Jump Game IV is a hard coding problem on arrays, hash table and breadth-first search, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var minJumps = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Jump Game IV — Solution in Python, Java & C++

Jump Game IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Jump Game IV is a hard coding problem on arrays, hash table and breadth-first search, asked in Amazon, Google and Microsoft interviews.

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

Hints for Jump Game IV

  1. Hint 1

    Every jump costs 1, so this is a shortest-path problem — breadth-first search.

  2. Hint 2

    Group the indices by value so the "same value" jumps are found in O(1).

  3. Hint 3

    Once a value's group has been used, it can never help again; clear it.

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

  1. Bucket the indices by their value.
  2. BFS from index 0. When popping u, enqueue every unvisited index in arr[u]'s bucket, then delete the bucket.
  3. Also enqueue u - 1 and u + 1 if they are in range and unvisited.
  4. 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

Java

public static int minJumps(int[] arr) {
    int n = arr.length;
    if (n <= 1) return 0;
    Map<Integer, List<Integer>> byVal = new HashMap<>();
    for (int i = 0; i < n; i++) byVal.computeIfAbsent(arr[i], x -> new ArrayList<>()).add(i);
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[0] = 0;
    int[] q = new int[n];
    int head = 0, tail = 0;
    q[tail++] = 0;
    while (head < tail) {
        int u = q[head++];
        if (u == n - 1) return dist[u];
        List<Integer> bucket = byVal.remove(arr[u]);
        if (bucket != null) {
            for (int v : bucket) {
                if (dist[v] >= 0) continue;
                dist[v] = dist[u] + 1;
                q[tail++] = v;
            }
        }
        if (u - 1 >= 0 && dist[u - 1] < 0) { dist[u - 1] = dist[u] + 1; q[tail++] = u - 1; }
        if (u + 1 < n && dist[u + 1] < 0) { dist[u + 1] = dist[u] + 1; q[tail++] = u + 1; }
    }
    return -1;
}

C++

int minJumps(vector<int>& arr) {
    int n = (int) arr.size();
    if (n <= 1) return 0;
    unordered_map<int, vector<int>> byVal;
    for (int i = 0; i < n; i++) byVal[arr[i]].push_back(i);
    vector<int> dist(n, -1), q;
    dist[0] = 0;
    q.push_back(0);
    for (size_t head = 0; head < q.size(); head++) {
        int u = q[head];
        if (u == n - 1) return dist[u];
        auto it = byVal.find(arr[u]);
        if (it != byVal.end()) {
            for (int v : it->second) {
                if (dist[v] >= 0) continue;
                dist[v] = dist[u] + 1;
                q.push_back(v);
            }
            byVal.erase(it);
        }
        if (u - 1 >= 0 && dist[u - 1] < 0) { dist[u - 1] = dist[u] + 1; q.push_back(u - 1); }
        if (u + 1 < n && dist[u + 1] < 0) { dist[u + 1] = dist[u] + 1; q.push_back(u + 1); }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets