You are given an integer array nums of length n.
You start at index 0, and your goal is to reach index n - 1.
From any index i, you may perform one of the following operations:
i + 1 or i - 1, if the index is within bounds.nums[i] is a prime number p, you may instantly jump to any index j != i such that nums[j] % p == 0.Return the minimum number of jumps required to reach index n - 1.
Example 1:
Input: nums = [1,2,4,6]
Output: 2
Explanation:
One optimal sequence of jumps is:
i = 0. Take an adjacent step to index 1.i = 1, nums[1] = 2 is a prime number. Therefore, we teleport to index i = 3 as nums[3] = 6 is divisible by 2.Thus, the answer is 2.
Example 2:
Input: nums = [2,3,4,7,9]
Output: 2
Explanation:
One optimal sequence of jumps is:
i = 0. Take an adjacent step to index i = 1.i = 1, nums[1] = 3 is a prime number. Therefore, we teleport to index i = 4 since nums[4] = 9 is divisible by 3.Thus, the answer is 2.
Example 3:
Input: nums = [4,6,5,8]
Output: 3
Explanation:
0 → 1 → 2 → 3. Thus, the answer is 3.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 106Problem Overview: You start at index 0 of an array and want to reach the last index using the minimum number of jumps. Besides moving to adjacent indices, certain numbers allow prime-based teleportation, creating additional edges between positions that share prime factors.
Approach 1: Brute Force BFS with Pairwise Prime Check (O(n² log V) time, O(n) space)
Treat the array as an implicit graph where each index is a node. From index i, you can move to i-1, i+1, or any index whose value shares a prime factor with nums[i]. A straightforward solution runs Breadth-First Search and checks every other element to see if they share a prime factor using repeated factorization or gcd. BFS guarantees the first time you reach the last index is the minimum number of jumps. The downside is the repeated pairwise checks, which lead to O(n² log V) complexity in the worst case.
Approach 2: BFS with Prime Factor Hash Mapping (O(n log V) time, O(n + P) space)
The optimized solution avoids scanning the entire array for teleport candidates. First compute the prime factors for every value using basic number factorization or a sieve from Number Theory. Build a hash map from each prime factor to the list of indices containing that factor. During BFS, when you visit index i, iterate through the prime factors of nums[i] and instantly retrieve all indices connected through that prime using a hash table. Push those indices into the BFS queue and then clear the list for that prime so it is processed only once. This prevents repeated traversals and keeps the total work close to linear.
The BFS queue stores (index, steps). Each expansion adds neighbors i-1, i+1, and all teleport indices discovered from the prime map. A visited array prevents revisiting nodes. Clearing processed prime groups ensures each teleport edge is used only once, which is the key optimization.
Recommended for interviews: The BFS with prime-factor hashing is the expected solution. It demonstrates graph modeling, number factorization, and careful pruning to keep the complexity near O(n log V). Explaining the brute force approach first shows understanding of the graph structure, while the optimized version shows the ability to reduce redundant work using hashing and number theory.
First, we preprocess the list of prime factors for every number up to 10^6 and store them in factors.
Then we build a graph g. For each index i and each p \in factors[nums[i]], we add i to g[p]. In this way, we obtain the list of indices that can be reached by teleportation through each prime number p.
Next, we use breadth-first search to find the minimum number of jumps. We maintain a queue q to store the indices that can currently be reached, with only index 0 in q initially. Each time we pop an index i from q, if i is the target index n - 1, we return the current number of jumps. Otherwise, we add all indices in g[nums[i]] to q and remove them from g[nums[i]] to avoid repeated visits. At the same time, we also add the adjacent indices i + 1 and i - 1 to q if they are within bounds.
The time complexity is O(n log M), and the space complexity is O(n log M), where n is the length of the array, and M is the maximum value in the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force BFS with Pairwise Prime Check | O(n² log V) | O(n) | Useful for understanding the graph structure or when constraints are very small |
| BFS with Prime Factor Hash Mapping | O(n log V) | O(n + P) | General case. Efficient for large arrays by grouping indices by prime factors |
| BFS with Sieve Precomputation | O(n log V) | O(n + V) | Best when values are large and repeated factorization becomes expensive |
Minimum Jumps to Reach End via Prime Teleportation | Simplified | Leetcode 3629 | codestorywithMIK • codestorywithMIK • 9,668 views views
Watch 9 more video solutions →Practice Minimum Jumps to Reach End via Prime Teleportation with our built-in code editor and test cases.
Practice on FleetCode