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.In #3115 Maximum Prime Difference, the goal is to identify the largest difference between indices of elements that are prime numbers in the given array. The key observation is that the maximum index difference will always occur between the first prime and the last prime encountered in the array.
A practical strategy is to iterate through the array and check whether each value is prime using a helper function. A number is prime if it is greater than 1 and has no divisors up to sqrt(n). While scanning, record the index of the first prime and keep updating the index of the last prime found.
After the traversal, compute the difference between these two indices. This avoids unnecessary comparisons between all pairs and keeps the solution efficient. The overall time complexity depends on the primality check, typically O(n * sqrt(m)), where m is the maximum value in the array, while the space complexity remains constant.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single pass scan with prime check | O(n * sqrt(m)) | O(1) |
| Scan with precomputed primes (Sieve) | O(n + m log log m) | O(m) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Find all prime numbers in the <code>nums</code>.
Find the first and the last prime number in the <code>nums</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
A common method is to test divisibility from 2 up to the square root of the number. If no divisor is found, the number is prime. Since array values are usually small, this check is efficient enough for each element.
Problems like Maximum Prime Difference reflect common interview patterns involving array traversal and number theory basics. While the exact question may vary, similar logic-based prime and index problems can appear in coding interviews.
No special data structure is required. A simple array traversal with a helper function for primality checking is sufficient, along with variables to track the first and last prime indices.
The optimal approach is to scan the array once and track the first and last indices containing prime numbers. By computing the difference between these two indices, you get the maximum possible prime index gap without comparing every pair.