3629. Minimum Jumps to Reach End via Prime Teleportation

Array
BFS
Number Theory
Hash Table

TIME

O(M log log M + n log M), M = max(nums)

SPACE

O(M + n log M)

Intuition

Every move costs one jump, so this is a shortest-path problem on indices. Adjacent moves are simple, but teleport moves can be large: from a prime value p, we can jump to every index whose value is divisible by p.

The key optimization is to preprocess teleport destinations by prime divisor. Then BFS can expand a prime teleport group once and clear it, because expanding the same prime again would only repeat work.

Approach

Build the smallest-prime-factor array up to max(nums).
Identify which values in nums are prime; only those primes can be used as teleport sources.
For each index i, factor nums[i] into distinct prime factors.
If a factor p appears as a prime value in nums, add index i to teleports[p].
Run BFS from index 0.
From each index:
- visit i - 1
- visit i + 1
- if nums[i] is prime, visit every index in teleports[nums[i]]
After using a prime teleport list, clear it so it is never scanned again.

Complexity

Time: O(M log log M + n log M), where M = max(nums)
Space: O(M + n log M), for the smallest-prime-factor array and teleport lists

Edge Cases

n = 1 -> already at the target
No prime values -> only adjacent steps are possible
Prime at current index has no useful destination -> BFS still continues through adjacent steps
Repeated values and repeated prime factors -> each index is added once per distinct relevant factor

Code

from collections import defaultdict, deque
from typing import List


class Solution:
    def minJumps(self, nums: List[int]) -> int:
        """
        3629. Minimum Jumps to Reach End via Prime Teleportation
        Time: O(M log log M + n log M), M = max(nums)
        Space: O(M + n log M)
        """
        n = len(nums)
        if n == 1:
            return 0

        max_value = max(nums)
        spf = self._build_spf(max_value)
        prime_sources = {num for num in nums if self._is_prime(num, spf)}

        teleports = defaultdict(list)
        for i, num in enumerate(nums):
            for factor in self._prime_factors(num, spf):
                if factor in prime_sources:
                    teleports[factor].append(i)

        distance = [-1] * n
        distance[0] = 0
        queue = deque([0])

        while queue:
            i = queue.popleft()
            next_distance = distance[i] + 1

            for nei in (i - 1, i + 1):
                if 0 <= nei < n and distance[nei] == -1:
                    if nei == n - 1:
                        return next_distance
                    distance[nei] = next_distance
                    queue.append(nei)

            value = nums[i]
            if value in prime_sources:
                for nei in teleports[value]:
                    if nei != i and distance[nei] == -1:
                        if nei == n - 1:
                            return next_distance
                        distance[nei] = next_distance
                        queue.append(nei)
                teleports[value].clear()

        return distance[n - 1]

    def _build_spf(self, max_value: int) -> List[int]:
        spf = list(range(max_value + 1))
        if max_value >= 0:
            spf[0] = 0
        if max_value >= 1:
            spf[1] = 1

        factor = 2
        while factor * factor <= max_value:
            if spf[factor] == factor:
                for multiple in range(factor * factor, max_value + 1, factor):
                    if spf[multiple] == multiple:
                        spf[multiple] = factor
            factor += 1

        return spf

    def _is_prime(self, num: int, spf: List[int]) -> bool:
        return num >= 2 and spf[num] == num

    def _prime_factors(self, num: int, spf: List[int]) -> List[int]:
        factors = []

        while num > 1:
            factor = spf[num]
            factors.append(factor)
            while num % factor == 0:
                num //= factor

        return factors

import java.util.*;

/**
 * 3629. Minimum Jumps to Reach End via Prime Teleportation
 * Time: O(M log log M + n log M), M = max(nums)
 * Space: O(M + n log M)
 */
class Solution {
    public int minJumps(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }

        int maxValue = 0;
        for (int num : nums) {
            maxValue = Math.max(maxValue, num);
        }

        int[] spf = buildSpf(maxValue);
        Set<Integer> primeSources = new HashSet<>();
        for (int num : nums) {
            if (isPrime(num, spf)) {
                primeSources.add(num);
            }
        }

        Map<Integer, List<Integer>> teleports = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int factor : primeFactors(nums[i], spf)) {
                if (primeSources.contains(factor)) {
                    teleports.computeIfAbsent(factor, key -> new ArrayList<>()).add(i);
                }
            }
        }

        int[] distance = new int[n];
        Arrays.fill(distance, -1);
        distance[0] = 0;

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);

        while (!queue.isEmpty()) {
            int i = queue.poll();
            int nextDistance = distance[i] + 1;

            int left = i - 1;
            if (left >= 0 && distance[left] == -1) {
                if (left == n - 1) {
                    return nextDistance;
                }
                distance[left] = nextDistance;
                queue.offer(left);
            }

            int right = i + 1;
            if (right < n && distance[right] == -1) {
                if (right == n - 1) {
                    return nextDistance;
                }
                distance[right] = nextDistance;
                queue.offer(right);
            }

            int value = nums[i];
            if (primeSources.contains(value)) {
                List<Integer> destinations = teleports.getOrDefault(value, Collections.emptyList());
                for (int nei : destinations) {
                    if (nei != i && distance[nei] == -1) {
                        if (nei == n - 1) {
                            return nextDistance;
                        }
                        distance[nei] = nextDistance;
                        queue.offer(nei);
                    }
                }
                destinations.clear();
            }
        }

        return distance[n - 1];
    }

    private int[] buildSpf(int maxValue) {
        int[] spf = new int[maxValue + 1];
        for (int i = 0; i <= maxValue; i++) {
            spf[i] = i;
        }

        if (maxValue >= 1) {
            spf[1] = 1;
        }

        for (int factor = 2; factor * factor <= maxValue; factor++) {
            if (spf[factor] == factor) {
                for (int multiple = factor * factor; multiple <= maxValue; multiple += factor) {
                    if (spf[multiple] == multiple) {
                        spf[multiple] = factor;
                    }
                }
            }
        }

        return spf;
    }

    private boolean isPrime(int num, int[] spf) {
        return num >= 2 && spf[num] == num;
    }

    private List<Integer> primeFactors(int num, int[] spf) {
        List<Integer> factors = new ArrayList<>();

        while (num > 1) {
            int factor = spf[num];
            factors.add(factor);
            while (num % factor == 0) {
                num /= factor;
            }
        }

        return factors;
    }
}