#3115

Medium

LeetCode Problem Workspace

Maximum Prime Difference

Calculate the largest index gap between prime numbers in an array using array traversal and number theory insights efficiently.

array math number theory

Problem Statement

Given an integer array nums, determine the greatest distance between indices of two prime numbers. The primes may be identical or distinct and must exist in nums.

Return an integer representing this maximum difference. For example, nums = [4,2,9,5,3] produces 3 because the prime numbers at indices 1 and 4 are furthest apart.

Examples

Example 1

Input: nums = [4,2,9,5,3]

Output: 3

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

nums[2] is prime. Because there is just one prime number, the answer is |2 - 2| = 0 .

Constraints

1 <= nums.length <= 3 * 105
1 <= nums[i] <= 100
The input is generated such that the number of prime numbers in the nums is at least one.

Solution Approach

Prime Identification

Precompute all primes up to 100 using a simple sieve or direct checks. Then scan nums to record indices of prime numbers for distance calculations.

Index Tracking

Maintain the first and last prime indices while iterating. Update the maximum difference dynamically to avoid storing all prime positions unnecessarily.

Distance Computation

Compute the difference between the last and first prime index found. This guarantees the maximum index gap and handles single-prime arrays gracefully.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k) where n is nums.length and k is the upper limit of prime checks (≤100). Space complexity is O(1) if storing only first and last indices, or O(p) if storing all prime positions.

What Interviewers Usually Probe

Look for efficient prime detection within small bounded numbers.
Check if candidate solutions handle arrays with only one prime correctly.
Consider both edge cases and normal spreads of primes in the array.

Common Pitfalls or Variants

Common pitfalls

Failing to precompute primes, leading to repeated unnecessary calculations.
Incorrectly assuming two primes must be distinct for maximum difference.
Not handling arrays where a single prime exists, producing incorrect output.

Follow-up variants

Compute maximum distance between odd numbers instead of primes.
Find maximum difference between numbers satisfying a custom number-theory property.
Return both indices of the furthest prime numbers, not just the distance.

FAQ

How do you handle arrays with only one prime for Maximum Prime Difference?

If there is a single prime, the maximum distance is zero since both start and end indices are the same.

What is the fastest way to identify primes in nums?

Use a precomputed sieve for numbers up to 100 to quickly check each array element.

Does Maximum Prime Difference require primes to be distinct?

No, the maximum difference can involve the same prime number at different positions.

Can this approach be applied to larger ranges of numbers?

Yes, but sieve precomputation or optimized prime checks should scale with the upper limit of numbers in the array.

Why is this problem pattern labeled Array plus Math?

It combines linear array traversal with number-theory calculations for primes, reflecting the typical trade-offs in index and value computations.

terminal

Solution

Solution 1: Traversal

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.

1

2

3

4

5

6

7

8

9

10

11

12

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 - i

Continue Practicing

#3116 kth smallest amount with single denomination combination #3044 most frequent prime #3012 minimize length of array using operations