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] <= 108Problem Overview: You start at index 0 of an array and want to reach the last index using the minimum number of jumps. From index i, you can move to i + 1, i - 1, or any other index j where arr[i] == arr[j]. The challenge is finding the shortest path while avoiding repeated work when many elements share the same value.
Approach 1: Breadth-First Search (BFS) (Time: O(n), Space: O(n))
Treat the array as an implicit graph where each index is a node. From a node i, edges exist to i - 1, i + 1, and all indices with the same value. Build a hash map from value to list of indices, then run BFS starting from index 0. BFS guarantees the first time you reach the last index is the minimum number of jumps. Use a visited set to avoid revisiting indices. The expensive part is repeatedly scanning lists of equal values, which can cause redundant work if many elements share the same value. This approach demonstrates the graph modeling technique commonly used with Breadth-First Search problems.
Approach 2: Optimized BFS with Lazy Clearing (Time: O(n), Space: O(n))
The key optimization is preventing repeated traversal of equal-value groups. Use a hash table that maps each value to its indices. During BFS, when you process all jumps for a value (for example, every index where arr[i] == x), immediately clear that list from the map. This "lazy clearing" ensures the group is processed only once. Each index is pushed into the queue at most once, and each value group is scanned once, keeping the total complexity linear. This approach combines array traversal, fast hash table lookups, and BFS layer expansion to efficiently compute the shortest path.
Recommended for interviews: Interviewers expect the optimized BFS solution. Modeling the problem as a graph and using BFS shows you recognize the shortest-path pattern. Mentioning the naive BFS first demonstrates understanding of the graph structure, but the optimized version with lazy clearing proves you can eliminate redundant scans and achieve true O(n) performance.
In this approach, we use a Breadth-First Search (BFS) to find the minimum number of jumps required. We start from the first index and explore all possible indices we can jump to. We maintain a queue that helps us process nodes level by level, where each level represents a jump.
We use a map to track all indices with the same value to make efficient jumps to similar value indices. Once an index is processed, we clear it from our map entries to avoid unnecessary recalculation.
This Python solution uses BFS for level-order traversal. Each level in BFS corresponds to a jump. We utilize a deque for efficient pop from the queue and a set to track visited indices to avoid revisiting and redundant processing of indices. The defaultdict helps in storing and accessing indices sharing the same array values efficiently.
Time Complexity: O(n), where n is the length of the array. The worst-case scenario processes every element once.
Space Complexity: O(n), due to additional storage for graph mapping and visited set.
While the first BFS approach involved clearing the graph entry after processing, this approach incorporates an even lazier clearing technique. Instead of clearing as soon as we're done processing, we mark for future removal unless revisiting an edge is necessary. This maintains a balance between redundant work and excessive memory usage.
The C++ solution leverages an unordered_map for organizing jumps and a queue to perform BFS similar to the Java approach. The difference lies in simplifying memory operations with lazy eviction of processed nodes to maintain simpler code and potentially decrease memory overhead.
Time Complexity: O(n), because we explore each node a constant number of times.
Space Complexity: O(n), accommodating the graph structure and tracking nodes via additional containers.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search (BFS) | Time Complexity: O(n), where n is the length of the array. The worst-case scenario processes every element once. Space Complexity: O(n), due to additional storage for graph mapping and visited set. |
| Approach 2: Optimized BFS with Lazy Clearing | Time Complexity: O(n), because we explore each node a constant number of times. Space Complexity: O(n), accommodating the graph structure and tracking nodes via additional containers. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Basic) | O(n) | O(n) | Understanding the graph model of the problem and building the initial BFS solution. |
| Optimized BFS with Lazy Clearing | O(n) | O(n) | Preferred interview solution. Eliminates repeated scans of equal-value indices for true linear performance. |
Jump Game IV | Leetcode 1345 | Google | Microsoft | Adobe | Amazon | codestorywithMIK • codestorywithMIK • 7,703 views views
Watch 9 more video solutions →Practice Jump Game IV with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor