# Jump Game IV
**Difficulty:** HARD
[External](https://leetcode.com/problems/jump-game-iv)
Canonical: https://scaleengineer.com/dsa/problems/jump-game-iv
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Hash Table
---
## Problem
Given an array of integers `arr`, you are initially positioned at the first index of the array.

In one step you can jump from index `i` to index:

* `i + 1` where: `i + 1 < arr.length`.
* `i - 1` where: `i - 1 >= 0`.
* `j` where: `arr[i] == arr[j]` and `i != j`.

Return _the minimum number of steps_ to reach the **last index** of the array.

Notice that you can not jump outside of the array at any time.

**Example 1:**

**Input:** arr = [100,-23,-23,404,100,23,23,23,3,404]
**Output:** 3
**Explanation:** You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

**Example 2:**

**Input:** arr = [7]
**Output:** 0
**Explanation:** Start index is the last index. You do not need to jump.

**Example 3:**

**Input:** arr = [7,6,9,6,9,6,9,7]
**Output:** 1
**Explanation:** You can jump directly from index 0 to index 7 which is last index of the array.

**Constraints:**

* `1 <= arr.length <= 5 * 104`
* `-108 <= arr[i] <= 108`

# Approaches
## Naive Breadth-First Search (BFS)
This approach models the problem as finding the shortest path in an unweighted graph. The array indices act as vertices, and the allowed jumps represent the edges. A standard Breadth-First Search (BFS) is employed to traverse the graph level by level from the start index `0`. This guarantees finding the path with the minimum number of jumps. However, its performance degrades significantly on certain test cases.
**Time:** O(N^2) in the worst case. If an array consists of N/2 identical elements, processing each of them could involve iterating through N/2 other indices, leading to quadratic complexity. · **Space:** O(N), where N is the number of elements in the array. This is for storing the graph map, the queue, and the visited array.
**Pros:** Simple to understand and implement.; It's a direct application of BFS for shortest path problems on unweighted graphs.
**Cons:** This approach is too slow for inputs with many repeated elements, leading to a Time Limit Exceeded (TLE) error.; It performs a lot of redundant work by repeatedly scanning the list of same-valued indices.
### Explanation
The core idea is to treat the array indices as nodes in a graph and the possible jumps as edges. Since all jumps have a weight of 1 (they count as one step), BFS is a natural fit for finding the shortest path.

First, we pre-process the array to build an adjacency list-style map (`Map<Integer, List<Integer>>`). This map stores, for each unique value in the array, a list of all indices where that value appears. This allows for efficient lookups of the third type of jump.

The BFS starts with a queue containing the initial index `0`. We also use a `visited` array to avoid processing the same index multiple times. The search proceeds in levels, where each level corresponds to an increase in the number of jumps.

At each index `curr` dequeued, we consider all possible next jumps:
1.  `curr + 1` (if within bounds)
2.  `curr - 1` (if within bounds)
3.  All indices `j` found in our pre-processed map for the value `arr[curr]`.

Any neighbor that has not been visited is added to the queue for the next level of the search. The process continues until the last index (`n-1`) is reached.

The major drawback is the handling of same-value jumps. If a value appears `k` times, every time we visit one of these `k` indices, we iterate through the other `k-1` indices. This can lead to approximately `k*k` operations for that single value, causing the overall complexity to become O(N^2) in the worst case.

```java
class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                if (curr == n - 1) {
                    return steps;
                }

                // Jump to j where arr[i] == arr[j]
                List<Integer> neighborsWithSameValue = graph.get(arr[curr]);
                for (int neighbor : neighborsWithSameValue) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.add(neighbor);
                    }
                }

                // Jump to i + 1
                if (curr + 1 < n && !visited[curr + 1]) {
                    visited[curr + 1] = true;
                    queue.add(curr + 1);
                }

                // Jump to i - 1
                if (curr - 1 >= 0 && !visited[curr - 1]) {
                    visited[curr - 1] = true;
                    queue.add(curr - 1);
                }
            }
            steps++;
        }

        return -1; // Should not be reached
    }
}
```
### Algorithm
- Create a map where keys are array values and values are lists of indices with that value.
- Initialize a queue with the starting index `0` and a `visited` array.
- Perform a standard Breadth-First Search (BFS) starting from index `0`.
- In each step of the BFS, for a given index `i`, explore its neighbors: `i-1`, `i+1`, and all indices `j` where `arr[i] == arr[j]`.
- Add unvisited neighbors to the queue.
- The first time the last index is reached, the current number of steps is the minimum required.

## Optimized Breadth-First Search (BFS)
This approach refines the naive BFS by addressing its key performance bottleneck. The inefficiency comes from repeatedly processing the long lists of indices for frequently occurring values. The optimization is simple yet effective: once we have explored all jumps to indices with a certain value `v`, we have added all of them to the queue. There is no need to ever consider jumps to this group of indices again. By clearing the list of indices for value `v` from our map after the first time we use it, we ensure that this expensive operation is performed only once per value, reducing the overall time complexity to linear.
**Time:** O(N). Each index is visited once. The total work for same-value jumps across the entire algorithm is O(N) because each list in the map is processed at most once. · **Space:** O(N) for the map, queue, and visited array.
**Pros:** Efficient with a linear time complexity, capable of passing all test cases.; Fixes the core issue of the naive approach with a simple modification.
**Cons:** Slightly more complex than the naive BFS due to the map modification during traversal.
### Explanation
The overall structure is identical to the naive BFS: we build a map, use a queue, and a `visited` array. The change lies in how we handle the same-value jumps.

When the BFS dequeues an index `curr`, it explores its neighbors. After checking `curr-1` and `curr+1`, it looks for neighbors with the value `arr[curr]` in the map. It iterates through the list of such neighbors, adding any unvisited ones to the queue.

The optimization is applied immediately after this loop: we remove the entry for `arr[curr]` from the map (e.g., `map.remove(arr[curr])`). This means that if we later visit another index `k` where `arr[k]` is the same as `arr[curr]`, the map lookup will fail, and we will not waste time re-iterating through a list of nodes that have already been queued up for visiting.

This ensures that the total number of 'same-value' jump explorations is proportional to the number of indices, N, rather than N^2. Each index is pushed and popped from the queue once, and each edge (including the implicit 'same-value' edges) is traversed once, leading to an efficient O(N) solution.

```java
class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                if (curr == n - 1) {
                    return steps;
                }

                // Jump to j where arr[i] == arr[j] and clear list after use
                if (graph.containsKey(arr[curr])) {
                    for (int neighbor : graph.get(arr[curr])) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.add(neighbor);
                        }
                    }
                    graph.remove(arr[curr]);
                }

                // Jump to i + 1
                if (curr + 1 < n && !visited[curr + 1]) {
                    visited[curr + 1] = true;
                    queue.add(curr + 1);
                }

                // Jump to i - 1
                if (curr - 1 >= 0 && !visited[curr - 1]) {
                    visited[curr - 1] = true;
                    queue.add(curr - 1);
                }
            }
            steps++;
        }

        return -1; // Should not be reached
    }
}
```
### Algorithm
- Pre-process the array to create a map of values to their indices, same as the naive approach.
- Start a standard BFS from index `0`.
- When exploring neighbors for an index `i`, consider `i-1` and `i+1`.
- Then, look up the list of indices that have the same value as `arr[i]`.
- Add all unvisited indices from this list to the queue.
- **Crucially**, after processing this list for the value `arr[i]`, remove the entry for `arr[i]` from the map. This ensures that for any given value, its corresponding list of indices is processed only once.

## Bidirectional Breadth-First Search (BFS)
Bidirectional BFS is a sophisticated optimization that performs two simultaneous BFS searches—one forward from the start and one backward from the end. The search terminates as soon as the two search frontiers intersect. For a graph with a branching factor of `b` and a shortest path of length `d`, a standard BFS might explore `O(b^d)` nodes. Bidirectional BFS explores roughly `2 * b^(d/2)` nodes, which is often a much smaller search space. This can lead to a significant practical speedup.
**Time:** O(N). While the theoretical complexity is the same as the optimized BFS, the number of nodes visited is often much smaller, leading to better performance in practice. The worst-case is still visiting all nodes. · **Space:** O(N) to store the graph map, visited array, and the two sets for the search frontiers.
**Pros:** Theoretically and often practically the fastest approach by reducing the search space.; Excellent for problems where the shortest path is relatively long compared to the graph size.
**Cons:** Significantly more complex to implement correctly compared to a standard BFS.; The overhead of managing two frontiers might make it slightly slower for some specific graph structures, although it's generally faster.
### Explanation
This approach aims to reduce the search radius. Instead of one search expanding outwards from the start, we have two searches expanding towards each other.

We maintain two sets of nodes, `q_start` and `q_end`, representing the outermost layer of nodes reached from the start and end, respectively. We also use a `visited` array to prevent cycles and redundant processing.

In each iteration, we choose the smaller of the two sets to expand. Let's say `q_start` is smaller. We iterate through each node `curr` in `q_start` and find all its neighbors (adjacent and same-value). For each neighbor, we first check if it's in `q_end`. If it is, our searches have met, and we can compute the total steps and return. If not, and if the neighbor hasn't been visited, we add it to a `next_level` set and mark it as visited.

After iterating through all nodes in the smaller set, we replace that set with the `next_level` set we just built. We then increment our step counter and repeat the process, potentially swapping the roles of `q_start` and `q_end` if the other set is now smaller.

The same optimization of clearing the same-value lists from the map is crucial here as well to maintain an overall linear time complexity.

```java
class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);
        }

        Set<Integer> q_start = new HashSet<>();
        q_start.add(0);

        Set<Integer> q_end = new HashSet<>();
        q_end.add(n - 1);

        boolean[] visited = new boolean[n];
        visited[0] = true;
        visited[n - 1] = true;

        int steps = 0;

        while (!q_start.isEmpty()) {
            if (q_start.size() > q_end.size()) {
                Set<Integer> temp = q_start;
                q_start = q_end;
                q_end = temp;
            }

            Set<Integer> next_level = new HashSet<>();
            for (int curr : q_start) {
                // Same-value jumps
                if (graph.containsKey(arr[curr])) {
                    for (int neighbor : graph.get(arr[curr])) {
                        if (q_end.contains(neighbor)) return steps + 1;
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            next_level.add(neighbor);
                        }
                    }
                    graph.remove(arr[curr]);
                }

                // Adjacent jumps
                int[] adjacent = {curr - 1, curr + 1};
                for (int neighbor : adjacent) {
                    if (neighbor >= 0 && neighbor < n) {
                        if (q_end.contains(neighbor)) return steps + 1;
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            next_level.add(neighbor);
                        }
                    }
                }
            }
            q_start = next_level;
            steps++;
        }

        return -1;
    }
}
```
### Algorithm
- Set up the same value-to-indices map as in other approaches.
- Initialize two search frontiers (e.g., using Sets), one starting from index `0` (`q_start`) and one from index `n-1` (`q_end`).
- Use a single `visited` array to track nodes visited by either search.
- In each step, expand the smaller of the two frontiers to minimize work.
- To expand a frontier, generate all valid, unvisited neighbors for each node in it.
- Before adding a new neighbor to the next level's frontier, check if it has already been visited by the *other* search. If so, the two searches have met, and a shortest path is found.
- The total steps will be the sum of steps taken by both searches.
- Apply the same optimization of clearing the same-value index list from the map after use.

# Solutions
### Java

```java
class Solution { public int minJumps ( int [] arr ) { int n = arr . length ; if ( n <= 1 ) { return 0 ; } // store nodes with the same value together in a graph dictionary Map < Integer , List < Integer >> graph = new HashMap <>(); for ( int i = 0 ; i < n ; i ++) { graph . computeIfAbsent ( arr [ i ], v -> new LinkedList <>()). add ( i ); } List < Integer > curs = new LinkedList <>(); // store current layer curs . add ( 0 ); Set < Integer > visited = new HashSet <>(); int step = 0 ; // when current layer exists while (! curs . isEmpty ()) { List < Integer > nex = new LinkedList <>(); // iterate the layer for ( int node : curs ) { // check if index 'node' reached end index if ( node == n - 1 ) { return step ; } // 1. check same value for ( int child : graph . get ( arr [ node ])) { if (! visited . contains ( child )) { visited . add ( child ); nex . add ( child ); } } // clear the list to prevent redundant search graph . get ( arr [ node ]). clear (); // 2. check left/right neighbors if ( node + 1 < n && ! visited . contains ( node + 1 )) { visited . add ( node + 1 ); nex . add ( node + 1 ); } if ( node - 1 >= 0 && ! visited . contains ( node - 1 )) { visited . add ( node - 1 ); nex . add ( node - 1 ); } } curs = nex ; step ++; } return - 1 ; } } ////// class Solution { public int minJumps ( int [] arr ) { Map < Integer , List < Integer >> idx = new HashMap <>(); int n = arr . length ; for ( int i = 0 ; i < n ; ++ i ) { idx . computeIfAbsent ( arr [ i ], k -> new ArrayList <>()). add ( i ); } Deque < int []> q = new LinkedList <>(); Set < Integer > vis = new HashSet <>(); vis . add ( 0 ); q . offer ( new int [] { 0 , 0 }); while (! q . isEmpty ()) { int [] e = q . pollFirst (); int i = e [ 0 ], step = e [ 1 ]; if ( i == n - 1 ) { return step ; } int v = arr [ i ]; ++ step ; for ( int j : idx . getOrDefault ( v , new ArrayList <>())) { if (! vis . contains ( j )) { vis . add ( j ); q . offer ( new int [] { j , step }); } } idx . remove ( v ); if ( i + 1 < n && ! vis . contains ( i + 1 )) { vis . add ( i + 1 ); q . offer ( new int [] { i + 1 , step }); } if ( i - 1 >= 0 && ! vis . contains ( i - 1 )) { vis . add ( i - 1 ); q . offer ( new int [] { i - 1 , step }); } } return - 1 ; } }
```

### Python

```python
''' list.remove(v): for list, remove by value, the first occurrence of v del my_dict[v]: for dict, delete by key 'v' my_dict = {'a': 1, 'b': 2, 'c': 3} del my_dict['b'] print(my_dict) # {'a': 1, 'c': 3} my_dict.pop('b') my_dict = {'a': 1, 'b': 2, 'c': 3} val = my_dict.pop('b') print(my_dict) # {'a': 1, 'c': 3} print(val) # 2 my_dict.popitem() my_dict = {'a': 1, 'b': 2, 'c': 3} item = my_dict.popitem() print(my_dict) # {'a': 1, 'b': 2} print(item) # ('c', 3) filter() and lambda my_dict = {'a': 1, 'b': 2, 'c': 3} my_dict = dict(filter(lambda item: item[0] != 'b', my_dict.items())) print(my_dict) # {'a': 1, 'c': 3} ''' from collections import deque class Solution : def minJumps ( self , arr : List [ int ]) -> int : idx = defaultdict ( list ) for i , v in enumerate ( arr ): idx [ v ]. append ( i ) q = deque ([( 0 , 0 )]) # (index, step) vis = { 0 } # visited while q : i , step = q . popleft () if i == len ( arr ) - 1 : return step v = arr [ i ] step += 1 for j in idx [ v ]: if j not in vis : vis . add ( j ) q . append (( j , step )) # without this del, it will be huge/duplicated loop # over time limit for input [7,7,7,7,7,....7,7] del idx [ v ] # avoid dedup if i + 1 < len ( arr ) and ( i + 1 ) not in vis : vis . add ( i + 1 ) q . append (( i + 1 , step )) if i - 1 >= 0 and ( i - 1 ) not in vis : vis . add ( i - 1 ) q . append (( i - 1 , step ))
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/jump-game-iv/ // Time: O(N) // Space: O(N) class Solution { public: int minJumps ( vector < int >& A ) { unordered_map < int , vector < int >> m ; int N = A . size (), step = 0 ; for ( int i = 0 ; i < N ; ++ i ) m [ A [ i ]]. push_back ( i ); vector < bool > seen ( N ); seen [ 0 ] = true ; queue < int > q { { 0 } }; while ( q . size ()) { int cnt = q . size (); while ( cnt -- ) { int u = q . front (); q . pop (); if ( u == N - 1 ) return step ; if ( u - 1 >= 0 && ! seen [ u - 1 ]) { q . push ( u - 1 ); seen [ u - 1 ] = true ; } if ( u + 1 < N && ! seen [ u + 1 ]) { q . push ( u + 1 ); seen [ u + 1 ] = true ; } if ( m . count ( A [ u ])) { for ( int v : m [ A [ u ]]) { if ( seen [ v ]) continue ; seen [ v ] = true ; q . push ( v ); } m . erase ( A [ u ]); } } ++ step ; } return - 1 ; } };
```