LeetCode 3629 - Minimum Jumps to Reach End via Prime Teleportation

The problem gives an integer array nums of length n, where each index represents a node in a graph. The task is to start at index 0 and reach index n - 1 in the minimum number of moves. From any index i, there are two types of moves.

leetcodemediumarrayhash-tablemathbreadth-first-searchnumber-theory

LeetCode Problem 3629

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Breadth-First Search, Number Theory

Solution

Problem Understanding

The problem gives an integer array nums of length n, where each index represents a node in a graph. The task is to start at index 0 and reach index n - 1 in the minimum number of moves.

From any index i, there are two types of moves. The first is a simple adjacency move, where you can go to i - 1 or i + 1 if those indices exist. The second is a special teleportation rule that depends on number theory. If nums[i] is a prime number p, then you can teleport from index i to any other index j such that nums[j] is divisible by p.

The output is the minimum number of jumps required to reach the last index. Because every move has equal cost, this is a shortest path problem in an unweighted graph.

The constraints are large, with n up to 10^5 and values up to 10^6. This immediately rules out naive pairwise checking for teleportation edges, since a full graph construction would be too slow.

Important edge cases include arrays of size 1, arrays with no primes (no teleportation possible), arrays where teleportation instantly reaches the end, and cases where multiple primes overlap divisibility chains heavily.

Approaches

Brute-force approach

A direct approach models the problem as an explicit graph where each index connects to its neighbors and also to all valid teleportation targets. From each index i, if nums[i] is prime, we scan all j != i to check divisibility and build edges. Then we run BFS to find the shortest path.

This works logically because BFS on the full graph guarantees shortest path in an unweighted graph. However, building edges is extremely expensive. For each prime index, scanning all n elements leads to O(n^2) worst case construction, which is infeasible.

Key insight for optimal solution

The critical optimization is to reverse how teleportation edges are interpreted. Instead of, for each prime p, scanning all j such that nums[j] % p == 0, we precompute a mapping from primes to all indices whose values are divisible by that prime.

We factor each number into its distinct prime factors. Then for each prime factor p, we maintain a list of indices whose values are divisible by p. This allows teleportation in amortized linear time.

We then run BFS over indices, but we only expand each prime group once, because once we use teleportation for a prime, we never need to revisit it.

This transforms the problem into a multi-source BFS with precomputed factor buckets.

Comparison table

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n²) Explicit graph construction with full divisibility checks
Optimal O(n log A) O(n + A) BFS with prime factor buckets and sieve-based preprocessing

Algorithm Walkthrough

We solve the problem using BFS over indices with preprocessing based on prime factorization.

  1. First, we precompute the smallest prime factor or use a sieve to efficiently factor numbers up to 10^6. This is necessary because we need fast prime decomposition for every value in nums.
  2. For each index i, we compute the distinct prime factors of nums[i]. Each prime factor p indicates that this index belongs to a teleportation group for p.
  3. We build a hash map prime_to_indices, where each prime p maps to a list of indices i such that nums[i] % p == 0. This structure allows us to simulate teleportation edges without checking every pair.
  4. We initialize a BFS queue starting from index 0 and maintain a distance array initialized to infinity, except dist[0] = 0.
  5. We also maintain a visited array for indices and a separate visited set for primes. The reason for tracking primes separately is to ensure we only process teleportation groups once.
  6. During BFS, for each popped index i, we try three types of transitions: moving to i - 1, moving to i + 1, and teleportation using each prime factor of nums[i].
  7. For each prime factor p of nums[i], if it has not been used before, we iterate through all indices in prime_to_indices[p] and push them into the BFS queue. After processing, we mark p as used and clear its list to prevent repeated work.
  8. We continue BFS until we reach index n - 1, at which point we return the distance.

Why it works

The BFS guarantees the shortest path because all edges have equal weight. The key invariant is that each index is processed at most once at its minimum distance, and each prime teleportation group is expanded exactly once, ensuring no redundant traversals while preserving all valid shortest transitions.

Python Solution

from typing import List
from collections import defaultdict, deque
import math

class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0

        max_val = max(nums)

        spf = list(range(max_val + 1))
        for i in range(2, int(math.sqrt(max_val)) + 1):
            if spf[i] == i:
                for j in range(i * i, max_val + 1, i):
                    if spf[j] == j:
                        spf[j] = i

        def get_primes(x):
            res = set()
            while x > 1:
                p = spf[x]
                res.add(p)
                while x % p == 0:
                    x //= p
            return res

        prime_to_indices = defaultdict(list)
        prime_factors = [set() for _ in range(n)]

        for i, val in enumerate(nums):
            factors = get_primes(val)
            prime_factors[i] = factors
            for p in factors:
                prime_to_indices[p].append(i)

        dist = [-1] * n
        dist[0] = 0
        q = deque([0])
        visited_primes = set()

        while q:
            i = q.popleft()
            d = dist[i]

            if i == n - 1:
                return d

            for ni in (i - 1, i + 1):
                if 0 <= ni < n and dist[ni] == -1:
                    dist[ni] = d + 1
                    q.append(ni)

            for p in prime_factors[i]:
                if p in visited_primes:
                    continue
                visited_primes.add(p)

                for ni in prime_to_indices[p]:
                    if dist[ni] == -1:
                        dist[ni] = d + 1
                        q.append(ni)

                prime_to_indices[p].clear()

        return -1

Explanation of implementation

The solution starts by building a smallest prime factor sieve to enable fast factorization. Each number is decomposed into its unique prime factors, and indices are grouped by those primes.

The BFS then runs from index 0, exploring adjacent transitions and teleportation transitions. The visited_primes set ensures each teleportation group is expanded only once, which prevents repeated O(n) scans.

The dist array tracks shortest distance and also acts as a visited marker for indices.

Go Solution

package main

import (
	"container/list"
)

func minJumps(nums []int) int {
	n := len(nums)
	if n == 1 {
		return 0
	}

	maxVal := 0
	for _, v := range nums {
		if v > maxVal {
			maxVal = v
		}
	}

	spf := make([]int, maxVal+1)
	for i := 0; i <= maxVal; i++ {
		spf[i] = i
	}

	for i := 2; i*i <= maxVal; i++ {
		if spf[i] == i {
			for j := i * i; j <= maxVal; j += i {
				if spf[j] == j {
					spf[j] = i
				}
			}
		}
	}

	getPrimes := func(x int) map[int]bool {
		res := make(map[int]bool)
		for x > 1 {
			p := spf[x]
			res[p] = true
			for x%p == 0 {
				x /= p
			}
		}
		return res
	}

	primeToIndices := make(map[int][]int)
	primeFactors := make([]map[int]bool, n)

	for i := 0; i < n; i++ {
		factors := getPrimes(nums[i])
		primeFactors[i] = factors
		for p := range factors {
			primeToIndices[p] = append(primeToIndices[p], i)
		}
	}

	dist := make([]int, n)
	for i := range dist {
		dist[i] = -1
	}
	dist[0] = 0

	q := list.New()
	q.PushBack(0)

	visitedPrime := make(map[int]bool)

	for q.Len() > 0 {
		front := q.Remove(q.Front()).(int)

		if front == n-1 {
			return dist[front]
		}

		for _, ni := range []int{front - 1, front + 1} {
			if ni >= 0 && ni < n && dist[ni] == -1 {
				dist[ni] = dist[front] + 1
				q.PushBack(ni)
			}
		}

		for p := range primeFactors[front] {
			if visitedPrime[p] {
				continue
			}
			visitedPrime[p] = true

			for _, ni := range primeToIndices[p] {
				if dist[ni] == -1 {
					dist[ni] = dist[front] + 1
					q.PushBack(ni)
				}
			}

			primeToIndices[p] = nil
		}
	}

	return -1
}

Go-specific notes

Go requires explicit handling of maps and slices, so the prime factor sets are represented as map[int]bool. BFS uses container/list instead of deque. Clearing teleportation groups is done by setting slices to nil to release references and avoid repeated work.

Worked Examples

Example 1: nums = [1,2,4,6]

Initially, BFS starts at index 0 with distance 0.

At index 0, no primes exist, so only index 1 is added with distance 1.

At index 1, value is 2, a prime. Prime 2 maps to indices 1, 2, and 3 (since 4 and 6 are divisible by 2). These are enqueued.

The BFS reaches index 3 at distance 2.

Step Queue Visited Distance
Start [0] {} [0, -1, -1, -1]
After 0 [1] {} [0, 1, -1, -1]
After 1 [2,3] {2-group} [0, 1, 2, 2]

Answer is 2.

Example 2: nums = [2,3,4,7,9]

Start at 0, move to 1.

At 1 (value 3), teleport via prime 3 to index 4.

Distance becomes 2.

Example 3: nums = [4,6,5,8]

No primes exist that unlock teleportation groups.

So BFS degenerates into linear traversal: 0 → 1 → 2 → 3.

Answer is 3.

Complexity Analysis

Measure Complexity Explanation
Time O(n log A) Each number is factorized once and each prime group is processed once
Space O(n + A) Storage for factor groups, sieve, and BFS state

The algorithm is efficient because each prime teleportation bucket is expanded only once, and factorization is amortized using preprocessing.

Test Cases

assert Solution().minJumps([1,2,4,6]) == 2  # basic teleportation case
assert Solution().minJumps([2,3,4,7,9]) == 2  # teleport to far index
assert Solution().minJumps([4,6,5,8]) == 3  # no teleportation useful
assert Solution().minJumps([1]) == 0  # single element
assert Solution().minJumps([2,4,8,16]) == 1  # immediate teleport chain
assert Solution().minJumps([5,10,15,25,30]) == 2  # dense prime 5 connections
Test Why
[1,2,4,6] validates basic teleportation
[2,3,4,7,9] validates long jump via prime
[4,6,5,8] validates no-teleport fallback
[1] single-node edge case
[2,4,8,16] dense divisibility chain
[5,10,15,25,30] heavy shared prime factor

Edge Cases

One important edge case is when the array has length one. In this case, the start is already at the destination, and the correct answer is zero. A BFS implementation must explicitly handle this to avoid unnecessary processing or invalid indexing.

Another edge case is when no element in the array is prime. In this situation, no teleportation edges exist at all, and the problem reduces to a simple shortest path along a line. The BFS should degrade gracefully into linear adjacency traversal without attempting factor-based expansions.

A third edge case occurs when many numbers share a common prime factor, such as all values being multiples of 2. Without careful pruning, teleportation would repeatedly reprocess the same group, leading to severe performance degradation. This is handled by marking each prime group as visited and clearing its adjacency list after first expansion, ensuring each teleportation bucket is processed exactly once.