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.
This approach uses the Sieve of Eratosthenes to precompute the prime numbers up to the maximum element in the nums array, which is 100. Then, it iterates over the given array to find indices of prime numbers, and calculates the maximum distance between any two prime indices.
The code first defines a sieve function to determine prime numbers up to 100. It initializes a list is_prime indicating primality and flags non-prime numbers using a nested loop. Next, it collects indices of prime numbers in the nums list. The maximum of this list minus the minimum gives the maximum distance between prime indices.
Time Complexity: O(n + m log log m), where n is the length of nums and m is the maximum number (100 here).
Space Complexity: O(m) due to the prime list.
This approach avoids precomputation of primes and checks if each number in nums is prime during the iteration. It collects indices of prime numbers and computes the maximum index difference.
This C++ code includes an isPrime function that checks the primality of a number. The function is optimized to check divisibility up to the square root of the number. The main function iterates through the array, accumulates prime indices, and computes the maximum index difference.
C++
JavaScript
Time Complexity: O(n√m), where n is the length of nums and m is the maximum number (up to 100).
Space Complexity: O(n) for storing prime indices.
According to the problem description, we need to find the index i of the first prime number, then find the index j of the last prime number, and return j - i as the answer.
Therefore, we can traverse the array from left to right to find the index i of the first prime number, then traverse the array from right to left to find the index j of the last prime number. The answer is j - i.
The time complexity is O(n times \sqrt{M}), where n and M are the length of the array nums and the maximum value in the array, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sieve of Eratosthenes and index tracking | Time Complexity: O(n + m log log m), where n is the length of nums and m is the maximum number (100 here). |
| Direct prime checking and index tracking | Time Complexity: O(n√m), where n is the length of |
| Traversal | — |
| 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. |
3115. Maximum Prime Difference | Prime Numbers | Array | Greedy • Aryan Mittal • 901 views views
Watch 6 more video solutions →Practice Maximum Prime Difference with our built-in code editor and test cases.
Practice on FleetCode