Skip to main content
Talentd

Maximum Prime Difference - Solution & Explanation

MediumArrayMathNumber Theory11 min readAsked at: Unstop
Practice this problem

Problem Statement

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 * 105
  • 1 <= nums[i] <= 100
  • The input is generated such that the number of prime numbers in the nums is at least one.

Approach Overview

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 1: Sieve of Eratosthenes and index tracking

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Direct prime checking and index tracking

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 3: 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.

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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).
Space Complexity: O(m) due to the prime list.

Direct prime checking and index tracking

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.

Traversalā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Prime Checking + Index TrackingO(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 TrackingO(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.

Video Solution

3115. Maximum Prime Difference | Prime Numbers | Array | Greedy ā€¢ Aryan Mittal ā€¢ 916 views views

Watch 5 more video solutions ā†’

Frequently Asked Questions

Is Maximum Prime Difference easy or hard?
Maximum Prime Difference is generally considered a medium-level problem. The logic is straightforward once you realize the maximum distance comes from the first and last primes, but the challenge comes from efficiently checking whether numbers are prime.
How to solve Maximum Prime Difference in O(n)?
First precompute prime numbers up to the maximum array value using the Sieve of Eratosthenes. Then perform a single O(n) pass through the array while looking up primality in the sieve table. Track the first and last prime indices and return their difference.
What is the best approach for Maximum Prime Difference?
The most practical approach scans the array while checking if each number is prime and tracks the first and last prime indices. The answer is simply lastPrimeIndex minus firstPrimeIndex. This runs in O(n * sqrt(m)) time where m is the maximum value in the array and uses O(1) extra space.
Is Maximum Prime Difference asked at Google/Amazon/Meta?
Problems involving prime detection, array scanning, and index tracking appear frequently in interviews at companies like Amazon and Google. While this exact problem may vary in wording, the underlying concepts from array processing and number theory are common interview topics.
What data structure is used in Maximum Prime Difference?
The core structure is a simple array traversal with index tracking. In the optimized version, a boolean array from the Sieve of Eratosthenes stores whether each number is prime, enabling constant-time prime checks.
What is the time complexity of Maximum Prime Difference?
The complexity depends on how primality is checked. Direct prime checking leads to O(n * sqrt(m)) time because each number may require checking divisors up to its square root. Using the Sieve of Eratosthenes reduces repeated checks and results in O(m log log m + n) time.
Maximum Prime Difference Python or Java solution approach?
In Python or Java, iterate through the array and use a helper function to check if each number is prime. Record the first index where a prime appears and keep updating the last index. After the loop, return the difference between those two indices.

Ready to solve this problem?

Practice Maximum Prime Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays