Problem Description

You are given an integer array nums.

Your task is to find the maximum distance between the indices of any two prime numbers in the array. The distance is calculated as the difference between their indices.

For example, if you have prime numbers at indices i and j where j > i, the distance would be j - i. You need to find the largest such distance possible.

Note that:

• The two prime numbers don't have to be different values (they can be the same prime number at different positions)
• You're looking for the distance between indices, not between the values themselves
• If there are multiple prime numbers in the array, you want to maximize the distance between any pair of them

The solution approach is straightforward: find the leftmost prime number's index and the rightmost prime number's index in the array, then return their difference. This guarantees the maximum distance since we're spanning from the earliest to the latest occurrence of prime numbers in the array.

Intuition

To maximize the distance between two prime numbers' indices, we need to think about what creates the largest gap. The distance between any two indices is simply j - i where j > i.

To maximize this difference, we want:

• i to be as small as possible (leftmost position)
• j to be as large as possible (rightmost position)

This leads us to a key insight: we don't need to check all pairs of prime numbers. The maximum distance will always be between the first prime number we encounter (smallest index) and the last prime number in the array (largest index).

Why? Because any other pair of primes would have either:

• A larger starting index (making i bigger, thus reducing j - i)
• A smaller ending index (making j smaller, thus reducing j - i)
• Or both

Therefore, our strategy becomes simple:

1. Find the first prime number while scanning from the left - this gives us the minimum possible i
2. Find the last prime number while scanning from the right - this gives us the maximum possible j
3. Return j - i

This greedy approach guarantees we find the maximum distance without needing to compare all possible pairs, making the solution efficient.

Learn more about Math patterns.

Solution Approach

The implementation follows a two-pointer approach to find the maximum distance between prime indices:

Step 1: Helper Function for Prime Checking

First, we define a helper function is_prime(x) to check if a number is prime:

• If x < 2, return False (0 and 1 are not prime)
• Check divisibility from 2 to sqrt(x). If x is divisible by any number in this range, it's not prime
• We only need to check up to sqrt(x) because if x has a divisor greater than sqrt(x), it must also have a corresponding divisor less than sqrt(x)

Step 2: Find the First Prime

We traverse the array from left to right using enumerate(nums):

• Check each element with is_prime(x)
• Once we find the first prime, we record its index i
• This gives us the leftmost prime position

Step 3: Find the Last Prime

After finding the first prime at index i, we search for the last prime:

• Start from the end of the array at index len(nums) - 1
• Traverse backwards until index i - 1 (we can stop at i - 1 because we already know there's a prime at index i)
• Check each element with is_prime(nums[j])
• The first prime we encounter while going backwards is the rightmost prime

Step 4: Calculate Maximum Distance

Once we find both indices:

• Return j - i as the maximum distance
• This works even if i == j (when there's only one prime in the array), giving a distance of 0

The algorithm has a time complexity of O(n * sqrt(m)) where n is the length of the array and m is the maximum value in the array (for prime checking). The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it finds the maximum distance between prime indices.

Example array: nums = [4, 2, 9, 5, 3, 8, 7, 10]

Step 1: Identify which numbers are prime

• Index 0: 4 → Not prime (divisible by 2)
• Index 1: 2 → Prime ✓
• Index 2: 9 → Not prime (divisible by 3)
• Index 3: 5 → Prime ✓
• Index 4: 3 → Prime ✓
• Index 5: 8 → Not prime (divisible by 2)
• Index 6: 7 → Prime ✓
• Index 7: 10 → Not prime (divisible by 2)

Step 2: Find the first (leftmost) prime Starting from index 0 and moving right:

• Index 0: 4 is not prime, continue
• Index 1: 2 is prime! Record i = 1

We found our leftmost prime at index 1.

Step 3: Find the last (rightmost) prime Starting from index 7 and moving left:

• Index 7: 10 is not prime, continue
• Index 6: 7 is prime! Record j = 6

We found our rightmost prime at index 6.

Step 4: Calculate the maximum distance Maximum distance = j - i = 6 - 1 = 5

Verification: Let's verify this is indeed the maximum by checking all possible prime pairs:

• Primes at indices: 1, 3, 4, 6
• Possible distances:
  • (1, 3): distance = 2
  • (1, 4): distance = 3
  • (1, 6): distance = 5 ← Maximum
  • (3, 4): distance = 1
  • (3, 6): distance = 3
  • (4, 6): distance = 2

As expected, the distance between the first prime (index 1) and the last prime (index 6) gives us the maximum distance of 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × √M)

The algorithm iterates through the array to find the first prime number, which takes O(n) iterations in the worst case. For each element checked, the is_prime function is called, which has a time complexity of O(√M) where M is the maximum value in the array. This is because is_prime checks divisibility from 2 up to √x.

Once the first prime is found at index i, the algorithm searches backwards from the end of the array to find the last prime. In the worst case, this requires checking O(n) elements again, with each check taking O(√M) time.

Therefore, the overall time complexity is O(n × √M), where n is the length of the array and M is the maximum value in the array.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The is_prime function uses a few variables for iteration and checking, and the main function uses variables i, j, and x for indexing and storing values. No additional data structures that scale with input size are created, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Prime Checking for Large Numbers

The current implementation checks primality by testing divisibility up to sqrt(n), which can be slow for large numbers. A common mistake is not optimizing the prime checking logic, leading to unnecessary computations.

Issue:

# Current approach checks all numbers from 2 to sqrt(n)
for divisor in range(2, int(sqrt(n)) + 1):
    if n % divisor == 0:
        return False

Solution: Optimize by checking 2 separately, then only odd numbers:

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
  
    # Only check odd divisors from 3 onwards
    for divisor in range(3, int(sqrt(n)) + 1, 2):
        if n % divisor == 0:
            return False
    return True

2. Unnecessary Full Array Traversal

A subtle inefficiency occurs when searching for the last prime. The code correctly stops at left_index - 1, but developers might mistakenly continue searching even after finding both primes.

Issue: Some might write nested loops that don't break properly:

# Inefficient: continues outer loop even after finding the answer
for i, x in enumerate(nums):
    if is_prime(x):
        for j in range(len(nums) - 1, i - 1, -1):
            if is_prime(nums[j]):
                max_dist = j - i  # Doesn't return immediately

Solution: Return immediately once both primes are found (as the current code correctly does).

3. Edge Case: Single Prime Number

While the current solution handles this correctly (returning 0 when i == j), developers might overlook this case and assume there are always at least two distinct prime positions.

Potential mistake:

# Wrong assumption: always different indices
first_prime = -1
last_prime = -1
# ... find primes ...
return last_prime - first_prime  # Could return negative if not handled properly

Solution: The current implementation correctly handles this by searching backwards from the end to left_index - 1, ensuring right_index >= left_index.

4. Integer Overflow in sqrt() Calculation

For very large numbers, int(sqrt(n)) might have precision issues. While rare in typical LeetCode constraints, it's worth considering.

Solution: Use integer-only arithmetic:

def is_prime(n: int) -> bool:
    if n < 2:
        return False
  
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0:
            return False
        divisor += 1 if divisor == 2 else 2
    return True