# Maximum Prime Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-prime-difference)
Canonical: https://scaleengineer.com/dsa/problems/maximum-prime-difference
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
You are given an integer array `nums`.

Return an integer that is the **maximum** distance between the **indices** of two (not necessarily different) prime numbers in `nums`_._

**Example 1:**

**Input:** nums = \[4,2,9,5,3\]

**Output:** 3

**Explanation:** `nums[1]`, `nums[3]`, and `nums[4]` are prime. So the answer is `|4 - 1| = 3`.

**Example 2:**

**Input:** nums = \[4,8,2,8\]

**Output:** 0

**Explanation:** `nums[2]` is prime. Because there is just one prime number, the answer is `|2 - 2| = 0`.

**Constraints:**

* `1 <= nums.length <= 3 * 105`
* `1 <= nums[i] <= 100`
* The input is generated such that the number of prime numbers in the `nums` is at least one.

# Approaches
## Brute-Force with Nested Loops
This approach iterates through all possible pairs of indices `(i, j)` in the array. For each pair, it checks if both `nums[i]` and `nums[j]` are prime numbers. If they are, it calculates the distance `j - i` and updates the maximum distance found so far. The primality test is done using trial division.
**Time:** O(N^2 * sqrt(M)), where `N` is the length of `nums` and `M` is the maximum value in `nums`. The nested loops contribute `O(N^2)`, and the `isPrime` check for each number takes `O(sqrt(M))`. This is too slow for the given constraints. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Simple to conceptualize and implement.; Requires no extra space.
**Cons:** Extremely inefficient due to the O(N^2) complexity.; Will result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.
### Explanation
The core idea is to exhaustively check every combination of two numbers in the array. A helper function, `isPrime(num)`, is used to determine if a number is prime. This function typically uses trial division, checking for divisors from 2 up to the square root of the number. The main function has two nested loops. The outer loop iterates from `i = 0` to `n-1`, and the inner loop from `j = i` to `n-1`. Inside the inner loop, we call `isPrime(nums[i])` and `isPrime(nums[j])`. If both are true, we update our answer: `max_dist = max(max_dist, j - i)`. This method is straightforward to understand but highly inefficient for large inputs.

```java
class Solution {
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public int maximumPrimeDifference(int[] nums) {
        int maxDist = 0;
        for (int i = 0; i < nums.length; i++) {
            if (isPrime(nums[i])) {
                for (int j = i; j < nums.length; j++) {
                    if (isPrime(nums[j])) {
                        maxDist = Math.max(maxDist, j - i);
                    }
                }
            }
        }
        return maxDist;
    }
}
```
### Algorithm
1. Initialize `maxDistance = 0`.
2. Create a helper function `isPrime(n)` that returns `true` if `n` is prime, `false` otherwise. This function checks for divisibility from 2 up to `sqrt(n)`.
3. Use a nested loop structure. The outer loop iterates with index `i` from `0` to `nums.length - 1`.
4. The inner loop iterates with index `j` from `i` to `nums.length - 1`.
5. Inside the inner loop, check if both `nums[i]` and `nums[j]` are prime by calling the `isPrime` helper function.
6. If both numbers are prime, update the maximum distance: `maxDistance = Math.max(maxDistance, j - i)`.
7. After the loops complete, return `maxDistance`.

## Single Pass with Trial Division
A much more efficient approach is to realize that the maximum distance will always be between the first prime number and the last prime number in the array. We don't need to check all pairs. This approach finds the index of the first prime and the last prime in a single pass over the array. The primality of each number is checked on-the-fly using a trial division helper function.
**Time:** O(N * sqrt(M)), where `N` is the length of `nums` and `M` is the maximum value in `nums`. We iterate through the array once (`O(N)`), and for each element, we perform a prime check (`O(sqrt(M))`). This is efficient enough to pass the given constraints. · **Space:** O(1), as we only use a few variables to store the indices.
**Pros:** Significantly faster than the brute-force approach.; Simple logic and easy to implement.; Constant space complexity.
**Cons:** The primality test is performed repeatedly for the same numbers if they appear multiple times in the array.; Slightly less performant than pre-computation for this specific problem's constraints.
### Explanation
The problem simplifies to finding `last_prime_index - first_prime_index`. We can find these two indices in a single pass through the array. We initialize a variable `firstPrimeIndex` to -1. We iterate through the array from left to right. The first time we encounter a prime number, we record its index in `firstPrimeIndex`. We also keep a `lastPrimeIndex` variable that gets updated every time we find a prime number. After iterating through the entire array, `firstPrimeIndex` will hold the index of the first prime, and `lastPrimeIndex` will hold the index of the last one. The prime check itself is done using a helper function with trial division.

```java
class Solution {
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public int maximumPrimeDifference(int[] nums) {
        int firstPrimeIndex = -1;
        int lastPrimeIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            if (isPrime(nums[i])) {
                if (firstPrimeIndex == -1) {
                    firstPrimeIndex = i;
                }
                lastPrimeIndex = i;
            }
        }
        return lastPrimeIndex - firstPrimeIndex;
    }
}
```
### Algorithm
1. Realize the maximum distance is between the first and last prime numbers.
2. Initialize `firstPrimeIndex = -1` and `lastPrimeIndex = -1`.
3. Create a helper function `isPrime(n)` that uses trial division to check for primality.
4. Iterate through the array `nums` with index `i` from `0` to `nums.length - 1`.
5. For each element `nums[i]`, call `isPrime(nums[i])`.
6. If `nums[i]` is prime:
   a. If `firstPrimeIndex` is still `-1`, set `firstPrimeIndex = i`.
   b. Always update `lastPrimeIndex = i`.
7. After the loop, the answer is `lastPrimeIndex - firstPrimeIndex`.

## Optimal Single Pass with Pre-computation (Sieve)
This is the most optimal approach. Given that the numbers in the array are small (up to 100), we can pre-compute all prime numbers up to 100 using the Sieve of Eratosthenes. This allows us to check if a number is prime in O(1) time (a simple array lookup). After the one-time pre-computation, we perform a single pass over the array to find the first and last prime indices, making the overall solution very fast.
**Time:** O(N + M*log(log(M))). The Sieve takes `O(M*log(log(M)))` time, where `M` is 100. The main loop takes `O(N)`. Since `M` is a small constant, the pre-computation is negligible, and the overall complexity is dominated by the loop, making it O(N). · **Space:** O(M), where `M` is the maximum possible value in `nums` (100 in this case). We use an array of size `M+1` to store the prime information. Since `M` is a small constant, this is effectively O(1) constant space.
**Pros:** The most efficient approach with linear time complexity.; The prime check is an O(1) operation after a one-time setup.; Perfectly suited for problems with a fixed, small range of input values.
**Cons:** Requires a small amount of extra space for the sieve array.; The code is slightly more complex due to the pre-computation step.
### Explanation
**Step 1: Pre-computation.** We create a boolean array, say `isPrime`, of size 101. We run the Sieve of Eratosthenes algorithm on this array. `isPrime[i]` will be `true` if `i` is a prime number and `false` otherwise. This step is done only once, and since the maximum value is 100, it's extremely fast.

**Step 2: Find Indices.** We then perform the same single-pass logic as the previous approach. We iterate through `nums`, but instead of calling a `isPrime` function that does trial division, we just look up `isPrime[nums[i]]`. This lookup is an O(1) operation. We find the first and last indices of prime numbers and return their difference.

```java
import java.util.Arrays;

class Solution {
    private static final int MAX_VAL = 100;
    private static final boolean[] isPrime = new boolean[MAX_VAL + 1];

    // Static initializer block to pre-compute primes using Sieve
    static {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= MAX_VAL; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= MAX_VAL; i += p) {
                    isPrime[i] = false;
                }
            }
        }
    }

    public int maximumPrimeDifference(int[] nums) {
        int firstPrimeIndex = -1;
        int lastPrimeIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            if (isPrime[nums[i]]) {
                if (firstPrimeIndex == -1) {
                    firstPrimeIndex = i;
                }
                lastPrimeIndex = i;
            }
        }
        // The problem guarantees at least one prime, so no need to check for -1.
        return lastPrimeIndex - firstPrimeIndex;
    }
}
```
### Algorithm
1. **Pre-computation:**
   a. Create a boolean array `isPrime` of size 101 (for values 1 to 100).
   b. Use the Sieve of Eratosthenes algorithm to populate this array. Initialize all to `true`, then mark `0` and `1` as not prime. Iterate from `p=2` and mark all multiples of `p` as not prime.
2. **Main Logic:**
   a. Initialize `firstPrimeIndex = -1` and `lastPrimeIndex = -1`.
   b. Iterate through `nums` from `i = 0` to `nums.length - 1`.
   c. For each `nums[i]`, check `isPrime[nums[i]]`. This is an O(1) lookup.
   d. If `isPrime[nums[i]]` is true:
      i. If `firstPrimeIndex == -1`, set `firstPrimeIndex = i`.
      ii. Update `lastPrimeIndex = i`.
3. Return `lastPrimeIndex - firstPrimeIndex`.

# Solutions
### Java

```java
class Solution { public int maximumPrimeDifference ( int [] nums ) { for ( int i = 0 ;; ++ i ) { if ( isPrime ( nums [ i ])) { for ( int j = nums . length - 1 ;; -- j ) { if ( isPrime ( nums [ j ])) { return j - i ; } } } } } private boolean isPrime ( int x ) { if ( x < 2 ) { return false ; } for ( int v = 2 ; v * v <= x ; ++ v ) { if ( x % v == 0 ) { return false ; } } return true ; } }
```

### CPP

```cpp
class Solution { public: int maximumPrimeDifference ( vector < int >& nums ) { for ( int i = 0 ;; ++ i ) { if ( isPrime ( nums [ i ])) { for ( int j = nums . size () - 1 ;; -- j ) { if ( isPrime ( nums [ j ])) { return j - i ; } } } } } bool isPrime ( int n ) { if ( n < 2 ) { return false ; } for ( int i = 2 ; i <= n / i ; ++ i ) { if ( n % i == 0 ) { return false ; } } return true ; } };
```

### Python

```python
class Solution : def maximumPrimeDifference ( self , nums : List [ int ]) -> int : def is_prime ( x : int ) -> bool : if x < 2 : return False return all ( x % i for i in range ( 2 , int ( sqrt ( x )) + 1 )) 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 ]): return j - i
```