Watch 7 video solutions for Maximum Prime Difference, a medium level problem involving Array, Math, Number Theory. This walkthrough by Aryan Mittal has 901 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100nums is at least one.Problem Overview: You are given an integer array nums. The goal is to find the maximum difference between the indices of two elements that are prime numbers. Since index difference grows as elements move farther apart, the optimal answer is simply the distance between the first and last prime numbers in the array.
Approach 1: Direct Prime Checking with Index Tracking (O(n * sqrt(m)) time, O(1) space)
Scan the array once while checking whether each value is prime. A number is prime if it has no divisors from 2 to sqrt(n). During the scan, store the index of the first prime encountered and keep updating the index of the most recent prime. After the traversal finishes, compute lastPrimeIndex - firstPrimeIndex. This approach works well when the array size is moderate and avoids extra memory. The key operations are a single array traversal and repeated prime checks using basic math and number theory principles.
Approach 2: Sieve of Eratosthenes + Index Tracking (O(m log log m + n) time, O(m) space)
Instead of checking primality for every element individually, precompute all prime numbers up to the maximum value in the array using the Sieve of Eratosthenes. The sieve builds a boolean lookup table where each index indicates whether the number is prime. After the sieve is built, iterate through the array once and check primality in O(1) time using the lookup table. Track the first and last indices containing prime values, then return their difference. This approach is faster when the array is large or contains repeated values because primality checks become constant-time lookups.
Recommended for interviews: The direct prime checking approach is usually sufficient and easier to implement during interviews. It demonstrates understanding of primality testing and efficient array traversal. The sieve-based approach shows stronger algorithmic awareness and becomes preferable when the value range is large or when many primality checks are required. Both solutions rely on the same insight: the maximum distance always occurs between the earliest and latest primes in the array.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Prime Checking + Index Tracking | O(n * sqrt(m)) | O(1) | Best when the array size is moderate and you want a simple implementation without extra memory. |
| Sieve of Eratosthenes + Index Tracking | O(m log log m + n) | O(m) | Useful when many numbers need primality checks or when the value range is large and repeated checks become expensive. |