Problem Statement in English

You’re given an array of integers nums. You start at index 0 and your goal is to reach index n - 1 in the minimum number of jumps.

There are two types of jumps you can make:

  • Adjacent Step: You can jump from index i to index i + 1 or index i - 1 if those indices are within the bounds of the array.

  • Prime Teleportation: If the number at index i is a prime number p, you can jump to any index j such that nums[j] is a multiple of p.

Return the minimum number of jumps required to reach index n - 1 from index 0. If it is not possible to reach the end, return -1.

Approach

There are a couple subproblems we need to solve here:

  1. We need to be able to quickly determine if a number is prime and also get its multiples so that we can try teleporting to each of them and later figuring out the quickest one that we can reach.

  2. We need to find the minimum number of jumps to reach the end. This is a classic shortest path problem in an unweighted graph, which can be solved using Breadth-First Search (BFS). The graph’s nodes are the indices of the array, and edges exist between adjacent indices and between indices that can be teleported to via prime numbers.

To solve the first subproblem, we can use a modified Sieve of Eratosthenes to precompute the smallest prime factor for each number up to the maximum value in nums. This allows us to quickly determine if a number is prime and is also extremely useful prime factorize a number, which we’re going to need to find the multiples of the prime numbers.

Next we iterate over the array and for each index, we find the prime factors of the number at that index and store the indices that are multiples of those prime factors in a mapping. This will allow us to quickly find all the indices we can teleport to from any given index.

Finally, we perform a BFS starting from index 0. For each index, we explore its adjacent indices and also the indices we can teleport to via prime numbers. We keep track of visited indices and visited primes to avoid cycles and redundant checks. The BFS continues until we reach index n - 1 or exhaust all possibilities.

And we’re done!

Solution in Python


class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        
        # 1. Pre-calculate primes up to the max value in nums using a sieve
        max_num = max(nums)
        min_prime = list(range(max_num + 1))
        for i in range(2, int(sqrt(max_num)) + 1):
            if min_prime[i] == i:
                for j in range(i*i, max_num + 1, i):
                    if min_prime[j] == j:
                        min_prime[j] = i
        
        def get_prime_factors(num):
            factors = []
            while num > 1:
                p = min_prime[num]
                factors.append(p)
                while num % p == 0:
                    num //= p
            return factors

        # 2. Map primes to indices that contain a multiple of that prime
        prime_to_indices = defaultdict(list)
        # Also map indices to their number's prime factors for Prime Teleportation
        index_to_primes = []
        
        for i, val in enumerate(nums):
            # Prime factorise the number at index i
            factors = get_prime_factors(val)
            # Store the prime factors for index i
            index_to_primes.append(factors)
            # Store each index that is a multiple of this prime factor
            for p in factors:
                prime_to_indices[p].append(i)

        # 3. BFS
        queue = deque([(0, 0)]) # (index, distance)
        visited_indices = {0}
        visited_primes = set()
        
        while queue:
            curr_idx, dist = queue.popleft()
            
            if curr_idx == n - 1:
                return dist
            
            # Option 1: Adjacent steps
            for neighbor in [curr_idx - 1, curr_idx + 1]:
                if 0 <= neighbor < n and neighbor not in visited_indices:
                    visited_indices.add(neighbor)
                    queue.append((neighbor, dist + 1))
            
            # Option 2: Prime Teleportation
            # Check if current number is prime
            val = nums[curr_idx]
            if val > 1 and min_prime[val] == val:
                p = val
                if p not in visited_primes:
                    visited_primes.add(p)
                    for next_idx in prime_to_indices[p]:
                        if next_idx not in visited_indices:
                            visited_indices.add(next_idx)
                            queue.append((next_idx, dist + 1))
                            
        return -1

Complexity

  • Time: $O(M \log \log M + N)$
    where $M$ is the maximum value in nums (for the sieve) and $N$ is the length of the input array (for the BFS and mappings). This is because the Sieve of Eratosthenes runs in $O(M \log \log M)$ time, and the BFS and mapping construction run in $O(N)$ time.

    The $O(M \log \log M)$ term comes from the sieve. Since we roughly $M$ numbers, and the number of multiples of each prime is $M/p$ for a prime $p$, the total work done across all primes is approximately $M \log \log M$, which by Mertens’ second theorem (the sum of reciprocals of primes) is asymptotically equivalent to $\log \log M$, and since we have $M$ numbers, it’s multiplied by $M$.

  • Space: $O(M + N)$
    where $M$ is the maximum value in nums (for the sieve) and $N$ is the length of the input array (for the BFS and mappings). This is because we need to store the smallest prime factor for each number up to $M$ and also the mappings of indices and primes.

Mistakes I Made

I had to look this one up :(

And we are done.