Maximum Prime Difference
MedPrompt
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 * 1051 <= nums[i] <= 100- The input is generated such that the number of prime numbers in the
numsis at least one.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
maxDistance = 0. - Create a helper function
isPrime(n)that returnstrueifnis prime,falseotherwise. This function checks for divisibility from 2 up tosqrt(n). - Use a nested loop structure. The outer loop iterates with index
ifrom0tonums.length - 1. - The inner loop iterates with index
jfromitonums.length - 1. - Inside the inner loop, check if both
nums[i]andnums[j]are prime by calling theisPrimehelper function. - If both numbers are prime, update the maximum distance:
maxDistance = Math.max(maxDistance, j - i). - After the loops complete, return
maxDistance.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Realize the maximum distance is between the first and last prime numbers.
- Initialize
firstPrimeIndex = -1andlastPrimeIndex = -1. - Create a helper function
isPrime(n)that uses trial division to check for primality. - Iterate through the array
numswith indexifrom0tonums.length - 1. - For each element
nums[i], callisPrime(nums[i]). - If
nums[i]is prime: a. IffirstPrimeIndexis still-1, setfirstPrimeIndex = i. b. Always updatelastPrimeIndex = i. - After the loop, the answer is
lastPrimeIndex - firstPrimeIndex.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Pre-computation:
a. Create a boolean array
isPrimeof size 101 (for values 1 to 100). b. Use the Sieve of Eratosthenes algorithm to populate this array. Initialize all totrue, then mark0and1as not prime. Iterate fromp=2and mark all multiples ofpas not prime. - Main Logic:
a. Initialize
firstPrimeIndex = -1andlastPrimeIndex = -1. b. Iterate throughnumsfromi = 0tonums.length - 1. c. For eachnums[i], checkisPrime[nums[i]]. This is an O(1) lookup. d. IfisPrime[nums[i]]is true: i. IffirstPrimeIndex == -1, setfirstPrimeIndex = i. ii. UpdatelastPrimeIndex = i. - Return
lastPrimeIndex - firstPrimeIndex.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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 ; } };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 - iVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.