Watch 9 video solutions for Minimum Jumps to Reach End via Prime Teleportation, a medium level problem involving Array, Hash Table, Math. This walkthrough by Leet's Code has 629 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |