Skip to main content
Talentd

Minimum Jumps to Reach End via Prime Teleportation - Solution & Explanation

MediumArrayHash TableMathBreadth-First Search11 min readAsked at: Amazon, Meta, Uber +1
Practice this problem

Problem Statement

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:

  • Adjacent Step: Jump to index i + 1 or i - 1, if the index is within bounds.
  • Prime Teleportation: If 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:

  • Start at index i = 0. Take an adjacent step to index 1.
  • At index 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:

  • Start at index i = 0. Take an adjacent step to index i = 1.
  • At index 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:

  • Since no teleportation is possible, we move through 0 → 1 → 2 → 3. Thus, the answer is 3.

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 1 <= nums[i] <= 106

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BFS with Pairwise Prime CheckO(n² log V)O(n)Useful for understanding the graph structure or when constraints are very small
BFS with Prime Factor Hash MappingO(n log V)O(n + P)General case. Efficient for large arrays by grouping indices by prime factors
BFS with Sieve PrecomputationO(n log V)O(n + V)Best when values are large and repeated factorization becomes expensive

Video Solution

Minimum Jumps to Reach End via Prime Teleportation | Simplified | Leetcode 3629 | codestorywithMIK • codestorywithMIK • 9,668 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Jumps to Reach End via Prime Teleportation easy or hard?
The problem is typically rated Medium. The BFS portion is straightforward, but recognizing that teleport edges can be grouped by prime factors and optimized with hashing and number theory is the key challenge.
Minimum Jumps to Reach End via Prime Teleportation Python/Java solution
Implement BFS starting from index 0. Factorize each array value and store indices grouped by their prime factors in a hash map. During traversal, push adjacent indices and teleport indices into the queue, marking visited nodes and clearing processed prime groups for efficiency.
How to solve Minimum Jumps to Reach End via Prime Teleportation in O(n)?
Model the array as a graph and run BFS from index 0. Precompute prime factors for each value and store indices in a hash map keyed by prime factor. During BFS, jump to neighbors i-1, i+1, and all indices sharing a prime factor, then clear that factor's list to avoid repeated processing.
What is the best approach for Minimum Jumps to Reach End via Prime Teleportation?
The most efficient approach uses Breadth-First Search combined with a hash map from prime factors to array indices. Each index is treated as a graph node, and teleport edges are created between indices sharing a prime factor. By processing each prime group only once, the algorithm runs in about O(n log V) time.
Is Minimum Jumps to Reach End via Prime Teleportation asked at Google/Amazon/Meta?
Problems combining BFS with number theory and hash maps appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of graph traversal with teleport rules are common because they test graph modeling, optimization, and data structure design.
What data structure is used in Minimum Jumps to Reach End via Prime Teleportation?
The solution primarily uses a queue for Breadth-First Search, a hash table mapping prime factors to indices, and a visited array to prevent revisiting nodes. Prime factorization or sieve preprocessing is also used to identify teleport connections.
What is the time complexity of Minimum Jumps to Reach End via Prime Teleportation?
The optimized solution runs in O(n log V) time where n is the array length and V is the maximum value in the array. The log V factor comes from prime factorization. Space complexity is O(n + P) for the BFS queue, visited array, and prime-to-indices hash map.

Ready to solve this problem?

Practice Minimum Jumps to Reach End via Prime Teleportation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays