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.
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 ; } }Video 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.