Jump Game IV — Editorial

Opening the reading…

Intuitionwhy equal-value jumps need to be consumed once

Think of every array index as a graph node. From index i, you can move to its neighboring indices and to every other index containing the same value. The requested minimum number of moves is therefore the shortest path from index 0 to index n - 1, which is exactly what breadth-first search computes in an unweighted graph.

The neighboring edges are cheap because each index has at most two of them. Equal-value edges are different: a value may occur at many indices, so scanning its whole group every time you stand on that value can repeat the same work many times. The first time BFS reaches any index with value x, scan all indices holding x, enqueue the unvisited ones, and then discard that group. Every later index with value x still has access to the same destinations, but scanning them again cannot reveal a shorter path.

BFS treats each equal-value list as one expandable group, not as a fresh list at every index.

Approach

Build a map from each array value to all indices containing it, because this turns the many possible equal-value jumps from any index into one list that can be expanded directly.

Create a distance array filled with -1 and a queue containing index 0 at distance 0, because BFS must record when an index is first reached and process positions in shortest-path order.

Remove the next index from the queue and return its distance if it is the last index, because the first time BFS removes the destination, no later layer can produce a shorter route.

Try index i + 1 and index i - 1 when they are inside the array and unvisited, because these are the two ordinary moves and omitting either one loses valid paths.

Look up the list for arr[i], enqueue every still-unvisited index in that list with distance dist[i] + 1, because every equal-value position is reachable in one move from i.

Erase arr[i]'s list after expanding it, because every index with that value has the same destinations and rescanning the list would repeat work without improving any distance.

Continue until the queue is empty and return the recorded distance, because an exhausted BFS has explored every reachable index and the destination is then unreachable.

Complexitythe group erase is what prevents repeated scans

MEASURE	BOUND	WHY
Time	O(n)	Building the value-to-indices map touches each index once. BFS enqueues each index at most once, and each equal-value list is scanned and erased only once, so the total number of list entries scanned is n; neighbor checks add at most 2n more operations.
Space	O(n)	The distance array, queue, and value-to-indices lists together store O(n) index entries, and the hash map has at most n keys. The method returns an integer, so there is no output array to exclude; the O(n) bound is already the worst case, including all values distinct or all values equal.

Here n is the length of arr. The bounds use the usual expected constant-time behavior of unordered_map operations.

Annotated solutionC++ · iterative breadth-first search with one-time group expansion

CPPBuild value groups, run BFS from index 0, and erase each group immediately after expanding it.

#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = static_cast<int>(arr.size());
        if (n == 1) {
            return 0;
        }

        unordered_map<int, vector<int>> same;
        for (int i = 0; i < n; ++i) {
            same[arr[i]].push_back(i);
        }

        vector<int> dist(n, -1);
        queue<int> q;
        q.push(0);
        dist[0] = 0;

        while (!q.empty()) {
            int i = q.front();
            q.pop();

            if (i == n - 1) {
                return dist[i];
            }

            if (i + 1 < n && dist[i + 1] == -1) {
                dist[i + 1] = dist[i] + 1;
                q.push(i + 1);
            }

            if (i - 1 >= 0 && dist[i - 1] == -1) {
                dist[i - 1] = dist[i] + 1;
                q.push(i - 1);
            }

            auto it = same.find(arr[i]);
            if (it != same.end()) {
                for (int j : it->second) {
                    if (dist[j] == -1) {
                        dist[j] = dist[i] + 1;
                        q.push(j);
                    }
                }
                same.erase(it);
            }
        }

        return -1;
    }
};

The key placement is the erase after the group loop. It is safe because all indices in the group have identical value-based destinations, so any later index with that value would discover exactly the same set. Neighbor moves remain available through the separate i + 1 and i - 1 checks, so erasing the value group removes only redundant equal-value scans, not valid movement.