Maximum Prime Difference solution and explanation
5 more videos on this problem
3115. Maximum Prime Difference | Prime Numbers | Array | GreedyAryan Mittal · 3:37 · 916 views
3115. Maximum Prime Difference | One pass solution | LeetCode Weekly Contest 393 | C++Priyanshi Porwal · 9:41 · 235 views
3115. Maximum Prime Difference (Leetcode Medium)Programming Live with Larry · 4:13 · 195 views
3115. Maximum Prime Difference #leetcode #coding #codingsolutions #amazoninterviewpreparationCodeVia · 2:34 · 46 views
Maximum Prime Difference | Leetcode 3115 | Binary Search Approach | Weekly Contest 393Aman Baluni · 7:53 · 42 views
DECODE DSA #LEVEL UP #CONTEST SOL.#leetcode#challenge#Maximum Prime Difference#LC-3115Decode · 5:19 · 22 views
The problem
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] <= 100- The input is generated such that the number of prime numbers in the
numsis 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.
def max_prime_diff(nums):
def sieve(max_num):
is_prime = [True] * (max_num + 1)
p = 2
while (p * p <= max_num):
if is_prime[p]:
for i in range(p * p, max_num + 1, p):
is_prime[i] = False
p += 1
is_prime[0], is_prime[1] = False, False
return is_prime
max_num = 100
is_prime = sieve(max_num)
prime_indices = [i for i, num in enumerate(nums) if is_prime[num]]
if not prime_indices:
return 0
return max(prime_indices) - min(prime_indices)
# Example usage:
ums = [4,2,9,5,3]
print(max_prime_diff(nums)) # Output: 3import java.util.*;
public class MaxPrimeDiff {
public static int maxPrimeDiff(int[] nums) {
boolean[] isPrime = sieve(100);
ArrayList<Integer> primeIndices = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (isPrime[nums[i]]) {
primeIndices.add(i);
}
}
if (primeIndices.size() < 2) {
return 0;
}
return primeIndices.get(primeIndices.size() - 1) - primeIndices.get(0);
}
private static boolean[] sieve(int max) {
boolean[] isPrime = new boolean[max + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int p = 2; p * p <= max; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= max; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
public static void main(String[] args) {
int[] nums = {4, 2, 9, 5, 3};
System.out.println(maxPrimeDiff(nums)); // Output: 3
}
}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.
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.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
int maxPrimeDiff(vector<int>& nums) {
vector<int> primeIndices;
for (int i = 0; i < nums.size(); ++i) {
if (isPrime(nums[i])) {
primeIndices.push_back(i);
}
}
if (primeIndices.size() < 2) return 0;
return primeIndices.back() - primeIndices.front();
}
int main() {
vector<int> nums = {4, 2, 9, 5, 3};
cout << maxPrimeDiff(nums) << endl; // Output: 3
return 0;
}function isPrime(num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 === 0 || num % 3 === 0) return false;
for (let i = 5; i * i <= num; i += 6) {
if (num % i === 0 || num % (i + 2) === 0) return false;
}
return true;
}
function maxPrimeDiff(nums) {
let primeIndices = [];
for (let i = 0; i < nums.length; i++) {
if (isPrime(nums[i])) {
primeIndices.push(i);
}
}
if (primeIndices.length < 2) return 0;
return primeIndices[primeIndices.length - 1] - primeIndices[0];
}
// Example usage:
let nums = [4, 2, 9, 5, 3];
console.log(maxPrimeDiff(nums)); // Output: 3This 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.
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.
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).
function maximumPrimeDifference(nums: number[]): number {
const isPrime = (x: number): boolean => {
if (x < 2) {
return false;
}
for (let i = 2; i <= x / i; i++) {
if (x % i === 0) {
return false;
}
}
return true;
};
for (let i = 0; ; ++i) {
if (isPrime(nums[i])) {
for (let j = nums.length - 1; ; --j) {
if (isPrime(nums[j])) {
return j - i;
}
}
}
}
}func maximumPrimeDifference(nums []int) int {
for i := 0; ; i++ {
if isPrime(nums[i]) {
for j := len(nums) - 1; ; j-- {
if isPrime(nums[j]) {
return j - i
}
}
}
}
}
func isPrime(n int) bool {
if n < 2 {
return false
}
for i := 2; i <= n/i; i++ {
if n%i == 0 {
return false
}
}
return true
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
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.