Jump Game IV

Hard

#1249Time: 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.

Algorithms

Breadth-First Search

Data structures

Array Hash Table

Prompt

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 * 10⁴
-10⁸ <= arr[i] <= 10⁸

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

curr + 1 (if within bounds)
curr - 1 (if within bounds)
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.

1class Solution {2    public int minJumps(int[] arr) {3        int n = arr.length;4        if (n <= 1) {5            return 0;6        }7 8        Map<Integer, List<Integer>> graph = new HashMap<>();9        for (int i = 0; i < n; i++) {10            graph.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);11        }12 13        Queue<Integer> queue = new LinkedList<>();14        queue.add(0);15        boolean[] visited = new boolean[n];16        visited[0] = true;17        int steps = 0;18 19        while (!queue.isEmpty()) {20            int size = queue.size();21            for (int i = 0; i < size; i++) {22                int curr = queue.poll();23                if (curr == n - 1) {24                    return steps;25                }26 27                // Jump to j where arr[i] == arr[j]28                List<Integer> neighborsWithSameValue = graph.get(arr[curr]);29                for (int neighbor : neighborsWithSameValue) {30                    if (!visited[neighbor]) {31                        visited[neighbor] = true;32                        queue.add(neighbor);33                    }34                }35 36                // Jump to i + 137                if (curr + 1 < n && !visited[curr + 1]) {38                    visited[curr + 1] = true;39                    queue.add(curr + 1);40                }41 42                // Jump to i - 143                if (curr - 1 >= 0 && !visited[curr - 1]) {44                    visited[curr - 1] = true;45                    queue.add(curr - 1);46                }47            }48            steps++;49        }50 51        return -1; // Should not be reached52    }53}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int minJumps(int[] arr) {3        int n = arr.length;4        if (n <= 1) {5            return 0;6        }7 8        Map<Integer, List<Integer>> graph = new HashMap<>();9        for (int i = 0; i < n; i++) {10            graph.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);11        }12 13        Queue<Integer> queue = new LinkedList<>();14        queue.add(0);15        boolean[] visited = new boolean[n];16        visited[0] = true;17        int steps = 0;18 19        while (!queue.isEmpty()) {20            int size = queue.size();21            for (int i = 0; i < size; i++) {22                int curr = queue.poll();23                if (curr == n - 1) {24                    return steps;25                }26 27                // Jump to j where arr[i] == arr[j] and clear list after use28                if (graph.containsKey(arr[curr])) {29                    for (int neighbor : graph.get(arr[curr])) {30                        if (!visited[neighbor]) {31                            visited[neighbor] = true;32                            queue.add(neighbor);33                        }34                    }35                    graph.remove(arr[curr]);36                }37 38                // Jump to i + 139                if (curr + 1 < n && !visited[curr + 1]) {40                    visited[curr + 1] = true;41                    queue.add(curr + 1);42                }43 44                // Jump to i - 145                if (curr - 1 >= 0 && !visited[curr - 1]) {46                    visited[curr - 1] = true;47                    queue.add(curr - 1);48                }49            }50            steps++;51        }52 53        return -1; // Should not be reached54    }55}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int minJumps(int[] arr) {3        int n = arr.length;4        if (n <= 1) {5            return 0;6        }7 8        Map<Integer, List<Integer>> graph = new HashMap<>();9        for (int i = 0; i < n; i++) {10            graph.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);11        }12 13        Set<Integer> q_start = new HashSet<>();14        q_start.add(0);15 16        Set<Integer> q_end = new HashSet<>();17        q_end.add(n - 1);18 19        boolean[] visited = new boolean[n];20        visited[0] = true;21        visited[n - 1] = true;22 23        int steps = 0;24 25        while (!q_start.isEmpty()) {26            if (q_start.size() > q_end.size()) {27                Set<Integer> temp = q_start;28                q_start = q_end;29                q_end = temp;30            }31 32            Set<Integer> next_level = new HashSet<>();33            for (int curr : q_start) {34                // Same-value jumps35                if (graph.containsKey(arr[curr])) {36                    for (int neighbor : graph.get(arr[curr])) {37                        if (q_end.contains(neighbor)) return steps + 1;38                        if (!visited[neighbor]) {39                            visited[neighbor] = true;40                            next_level.add(neighbor);41                        }42                    }43                    graph.remove(arr[curr]);44                }45 46                // Adjacent jumps47                int[] adjacent = {curr - 1, curr + 1};48                for (int neighbor : adjacent) {49                    if (neighbor >= 0 && neighbor < n) {50                        if (q_end.contains(neighbor)) return steps + 1;51                        if (!visited[neighbor]) {52                            visited[neighbor] = true;53                            next_level.add(neighbor);54                        }55                    }56                }57            }58            q_start = next_level;59            steps++;60        }61 62        return -1;63    }64}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1''' 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 ))

1// 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 ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ; } }

1''' 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 ))

1// 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 ; } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.