LeetCode 3115 - Maximum Prime Difference

LeetCode Problem 3115

Difficulty: 🟡 Medium
Topics: Array, Math, Number Theory

Solution

Problem Understanding

The problem gives us an integer array nums, and we need to find the maximum distance between the indices of any two prime numbers in the array.

More specifically, we are interested in indices i and j such that both nums[i] and nums[j] are prime numbers. Among all such pairs, we want the maximum possible value of:

$$|i - j|$$

The problem explicitly says that the two prime numbers do not need to be different. This matters because if there is only one prime number in the array, we are allowed to choose the same index twice, producing a distance of 0.

The input array can contain up to:

$$3 \times 10^5$$

elements, which means the solution must be efficient. Fortunately, each number is small:

$$1 \le nums[i] \le 100$$

This small value range makes prime checking very cheap.

The key observation is that the maximum distance between prime indices will always come from the leftmost prime and the rightmost prime. If the first prime appears at index left and the last prime appears at index right, then:

$$\text{answer} = right - left$$

because any other prime index must lie between them.

Several edge cases are important:

• The array may contain exactly one prime number. In that case, the answer must be 0.
• Prime numbers may appear at the beginning or end of the array.
• Most values may be non-prime, so we must correctly skip them.
• The number 1 is not prime, which is a common source of bugs.
• Since values are at most 100, we can either precompute primes or use a small helper function for primality testing.

Approaches

Brute Force Approach

A straightforward solution is to first collect all indices whose values are prime numbers. Then we compare every pair of prime indices and compute their distance.

Suppose the prime indices are stored in:

$$[p_1, p_2, p_3, \dots]$$

We could use two nested loops to compute:

$$|p_j - p_i|$$

for every pair and keep track of the maximum.

This approach is correct because it explicitly checks every possible pair of prime indices. However, it is inefficient. If the array contains many primes, the number of comparisons becomes quadratic.

With up to 3 * 10^5 elements, an O(n^2) solution is far too slow.

Optimal Approach

The important insight is that we do not need to compare every pair.

The maximum distance between two indices always comes from the smallest index and the largest index among all prime positions. Therefore, we only need:

• The index of the first prime number
• The index of the last prime number

Once we know those two positions, the answer is simply:

$$lastPrimeIndex - firstPrimeIndex$$

We can scan the array once from left to right:

• When we encounter the first prime, record its index.
• Continue scanning and keep updating the last prime index whenever we find another prime.
• At the end, subtract the two indices.

This reduces the complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k²)	O(k)	Stores all prime indices and compares every pair
Optimal	O(n)	O(1)	Tracks only first and last prime indices

Here, k is the number of prime numbers in the array.

Algorithm Walkthrough

1. Create a helper function that determines whether a number is prime.

A prime number is greater than 1 and divisible only by 1 and itself. Since all values are at most 100, primality testing is very cheap. 2. Initialize two variables:

• first_prime_index = -1
• last_prime_index = -1

These variables will store the positions of the first and last prime numbers encountered during traversal. 3. Traverse the array from left to right.

For each element:

• Check whether the current value is prime.
• If it is prime and first_prime_index has not been assigned yet, store the current index as the first prime index.
• Always update last_prime_index to the current index whenever a prime is found.

4. After the traversal completes, compute:

$$last_prime_index - first_prime_index$$

1. Return the result.

Because the problem guarantees at least one prime number exists, both indices will always be valid by the end of the scan.

Why it works

The algorithm works because every prime index lies between the first prime index and the last prime index.

If:

$$first \le any_prime_index \le last$$

then the maximum possible distance between any two prime indices must be:

$$last - first$$

No other pair can produce a larger difference.

Python Solution

from typing import List

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        def is_prime(num: int) -> bool:
            if num < 2:
                return False

            for divisor in range(2, int(num ** 0.5) + 1):
                if num % divisor == 0:
                    return False

            return True

        first_prime_index = -1
        last_prime_index = -1

        for index, value in enumerate(nums):
            if is_prime(value):
                if first_prime_index == -1:
                    first_prime_index = index

                last_prime_index = index

        return last_prime_index - first_prime_index

The solution begins with the helper function is_prime. The function first rejects numbers smaller than 2, since 0 and 1 are not prime numbers.

To test primality efficiently, we only check divisors up to:

$$\sqrt{n}$$

If any divisor evenly divides the number, the number is not prime.

The main traversal iterates through the array using enumerate, which gives both the index and the value.

When a prime number is encountered:

• The first occurrence sets first_prime_index.
• Every occurrence updates last_prime_index.

At the end, the difference between these two indices is returned.

The implementation exactly follows the optimal algorithm discussed earlier.

Go Solution

func maximumPrimeDifference(nums []int) int {
	isPrime := func(num int) bool {
		if num < 2 {
			return false
		}

		for divisor := 2; divisor*divisor <= num; divisor++ {
			if num%divisor == 0 {
				return false
			}
		}

		return true
	}

	firstPrimeIndex := -1
	lastPrimeIndex := -1

	for index, value := range nums {
		if isPrime(value) {
			if firstPrimeIndex == -1 {
				firstPrimeIndex = index
			}

			lastPrimeIndex = index
		}
	}

	return lastPrimeIndex - firstPrimeIndex
}

The Go implementation follows the same logic as the Python version.

A closure named isPrime is used for primality testing. Instead of using square roots, the loop condition:

divisor*divisor <= num

efficiently checks up to the square root.

Go slices are used naturally for array traversal with the range keyword. Since the problem guarantees at least one prime number, there is no need for extra validation before returning the difference.

Integer overflow is not a concern because values are very small and indices are bounded by the array length.

Worked Examples

Example 1

Input:

nums = [4, 2, 9, 5, 3]

Prime numbers are:

• 2 at index 1
• 5 at index 3
• 3 at index 4

Traversal state:

Index	Value	Prime?	first_prime_index	last_prime_index
0	4	No	-1	-1
1	2	Yes	1	1
2	9	No	1	1
3	5	Yes	1	3
4	3	Yes	1	4

Final calculation:

$$4 - 1 = 3$$

Output:

3

Example 2

Input:

nums = [4, 8, 2, 8]

Prime numbers are:

• 2 at index 2

Traversal state:

Index	Value	Prime?	first_prime_index	last_prime_index
0	4	No	-1	-1
1	8	No	-1	-1
2	2	Yes	2	2
3	8	No	2	2

Final calculation:

$$2 - 2 = 0$$

Output:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is scanned once
Space	O(1)	Only a few variables are stored

The algorithm performs a single linear traversal of the array.

Although primality checking itself involves a loop, the maximum value is only 100, so the cost is effectively constant. Therefore, the overall complexity remains linear in the size of the array.

The space usage is constant because we only store a few integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.maximumPrimeDifference([4, 2, 9, 5, 3]) == 3
# Multiple primes, maximum span across array

assert solution.maximumPrimeDifference([4, 8, 2, 8]) == 0
# Only one prime number

assert solution.maximumPrimeDifference([2]) == 0
# Single-element array containing a prime

assert solution.maximumPrimeDifference([2, 3, 5, 7]) == 3
# All elements are prime

assert solution.maximumPrimeDifference([1, 4, 6, 8, 11]) == 0
# Only one prime at the end

assert solution.maximumPrimeDifference([13, 4, 6, 8, 9]) == 0
# Only one prime at the beginning

assert solution.maximumPrimeDifference([1, 2, 1, 3, 1, 5, 1]) == 5
# Primes separated by many non-prime values

assert solution.maximumPrimeDifference([97, 1, 1, 1, 2]) == 4
# Large valid prime values near bounds

assert solution.maximumPrimeDifference([1, 1, 1, 2, 1, 1]) == 0
# Exactly one prime surrounded by non-primes

assert solution.maximumPrimeDifference([4, 6, 8, 9, 10, 11, 12, 13]) == 2
# Two primes near the end

Test	Why
[4, 2, 9, 5, 3]	Standard case with multiple primes
[4, 8, 2, 8]	Only one prime exists
[2]	Smallest possible valid input
[2, 3, 5, 7]	Every element is prime
[1, 4, 6, 8, 11]	Single prime at the end
[13, 4, 6, 8, 9]	Single prime at the beginning
[1, 2, 1, 3, 1, 5, 1]	Primes separated by many non-primes
[97, 1, 1, 1, 2]	Tests upper bound prime values
[1, 1, 1, 2, 1, 1]	One isolated prime
[4, 6, 8, 9, 10, 11, 12, 13]	Two primes close together

Edge Cases

One important edge case occurs when the array contains exactly one prime number. A careless implementation might incorrectly return an invalid value or fail because there is no second prime index. The problem explicitly allows choosing the same index twice, so the correct answer is 0. The implementation handles this naturally because both first_prime_index and last_prime_index become the same value.

Another important edge case involves the number 1. Many incorrect primality implementations mistakenly classify 1 as prime. In this solution, the helper function immediately returns False for all numbers smaller than 2, ensuring correct behavior.

A third edge case occurs when prime numbers appear only at the boundaries of the array. For example:

[2, 4, 6, 8, 11]

The algorithm correctly records the first prime at index 0 and the last prime at index 4, producing the maximum possible distance.

A final edge case involves arrays where every number is prime. In such cases, the answer should simply be:

$$n - 1$$

because the first and last indices span the entire array. Since the algorithm always tracks the earliest and latest prime positions, it handles this scenario correctly without any special logic.