Find the minimum number of jumps needed to reach the end of an array when you can also teleport between prime-valued positions.
You are given an integer array nums of length n. Start at index 0 and want to reach index n - 1 using the fewest moves.
In one move, you may do either of the following:
- Jump from index
itoi - 1ori + 1if that index exists. - Teleport from index
ito any other indexjsuch thatnums[i]andnums[j]are both prime numbers and the two values satisfy the teleportation rule described by the problem instance.
Return the minimum number of moves required to reach the last index.
This is a shortest-path-in-unweighted-state-space problem. The key challenge is to model teleportation efficiently so that repeated prime-to-prime transitions do not become too expensive.
Input Format
nums: integer array of lengthn- Start index is
0 - Target index is
n - 1
Output Format
Return the minimum number of moves needed to reach index n - 1 from index 0.
Constraints
1 <= n <= $10^{5}$- Array values may be positive, zero, or negative depending on the instance
- Assume a move between two positions counts as 1
- If the end is unreachable, return
-1
Example 1
Input
nums = [2, 4, 5, 9, 11]
Output
2
Explanation
One optimal route is 0 -> 2 -> 4. The first step uses a teleport-style move between prime-valued positions, and the second step moves forward by adjacency.
Example 2
Input
nums = [1, 6, 8, 10, 12]
Output
4
Explanation
There are no useful prime-teleport options, so you must move by adjacent indices only: 0 -> 1 -> 2 -> 3 -> 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.