3115. Maximum Prime Difference

MediumArrayMathNumber Theory

Problem Description

You are given an integer array nums. Your task is to return an integer that represents the maximum distance between the indices of two (not necessarily different) prime numbers in nums.

Intuition

To solve this problem, you need to understand how prime numbers are identified and how to find the maximum distance between them in an array. The idea is to find the position (index) of the first prime number in the array from the beginning and the position of the last prime number from the end. The difference between these two indices gives the maximum distance.

First, traverse the array from left to right to locate the index of the first prime number.
Then, traverse the array from right to left to find the index of the last prime number.
The maximum distance is simply the difference between these two indices.

This approach efficiently uses two linear scans of the array, ensuring that we find both the first and last prime indices without unnecessary computations.

Learn more about Math patterns.

Solution Approach

The solution begins with defining a helper function is_prime(x: int) -> bool which checks if a number x is prime. A prime number is greater than 1 and divisible only by 1 and itself. Thus, for any number less than 2, it is not prime. For numbers greater than or equal to 2, the function checks divisibility from 2 up to the square root of the number. This optimization reduces the number of checks needed.

The main logic follows these steps:

First Prime Index (i):
- Traverse the array nums from the beginning (left to right).
- Use the is_prime function to find the first number that is prime.
- Record and store its index i when found.
Last Prime Index (j):
- Traverse the array nums from the end (right to left).
- Again, use the is_prime function to identify the first prime number encountered from this direction.
- Record and store its index j when found.
Calculate Maximum Distance:
- Once both indices i and j are found, compute the difference j - i.
- This difference represents the maximum distance between any two prime numbers in the array.

The traversal ensures that you find both the first and last prime indices with minimal computational overhead, primarily leveraging the efficiency of the is_prime check.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example array to demonstrate the solution approach: nums = [10, 3, 4, 7, 6, 11, 18].

First Prime Index (i):
- Start traversing the array from the beginning.
- Check if each number is a prime:
  - 10 is not prime.
  - 3 is prime (indices: 1).
- Record the index i = 1 because 3 is the first prime number encountered from the left.
Last Prime Index (j):
- Now, traverse the array from the end.
- Check if each number is a prime:
  - 18 is not prime.
  - 11 is prime (indices: 5).
- Record the index j = 5 because 11 is the first prime number encountered from the right.
Calculate Maximum Distance:
- Compute the maximum distance using the indices i = 1 and j = 5.
- The result is j - i = 5 - 1 = 4.

Thus, the maximum distance between the indices of two prime numbers in the array is 4.

Solution Implementation

1from typing import List
2from math import sqrt
3
4class Solution:
5    def maximumPrimeDifference(self, nums: List[int]) -> int:
6        # Helper function to check if a number is prime 
7        def is_prime(x: int) -> bool:
8            if x < 2:
9                return False
10            # Check divisibility from 2 up to the square root of the number
11            for i in range(2, int(sqrt(x)) + 1):
12                if x % i == 0:
13                    return False
14            return True
15
16        # Enumerate through the list of numbers to find the first prime
17        for i, x in enumerate(nums):
18            if is_prime(x):
19                # Search backwards from the end of the list for the next prime
20                for j in range(len(nums) - 1, i - 1, -1):
21                    if is_prime(nums[j]):
22                        # Return the difference in their indices
23                        return j - i
24        # If no such prime pair is found, return 0 (or handle based on requirements)
25        return 0
26

1class Solution {
2    // Method to find the maximum prime difference in the array
3    public int maximumPrimeDifference(int[] nums) {
4        // Loop from the start of the array
5        for (int i = 0; ; ++i) {
6            // Check if the current number is a prime number
7            if (isPrime(nums[i])) {
8                // Loop from the end of the array
9                for (int j = nums.length - 1; ; --j) {
10                    // Check if the current number is a prime number
11                    if (isPrime(nums[j])) {
12                        // Return the difference between the indices
13                        return j - i;
14                    }
15                }
16            }
17        }
18    }
19
20    // Helper method to check if a number is prime
21    private boolean isPrime(int number) {
22        // Numbers less than 2 are not prime
23        if (number < 2) {
24            return false;
25        }
26        // Check for factors from 2 to the square root of the number
27        for (int divisor = 2; divisor * divisor <= number; ++divisor) {
28            // If there's a divisor, the number is not prime
29            if (number % divisor == 0) {
30                return false;
31            }
32        }
33        // If no divisors found, the number is prime
34        return true;
35    }
36}
37

1class Solution {
2public:
3    // Function to calculate the maximum difference between indices of prime numbers.
4    int maximumPrimeDifference(std::vector<int>& nums) {
5        // Iterate through the vector from the beginning to find the first prime number
6        for (int i = 0;; ++i) {
7            if (isPrime(nums[i])) {
8                // Iterate through the vector from the end to find the last prime number
9                for (int j = nums.size() - 1;; --j) {
10                    if (isPrime(nums[j])) {
11                        // Return the difference between the indices of the last and first prime numbers
12                        return j - i;
13                    }
14                }
15            }
16        }
17    }
18
19    // Helper function to check if a number is prime
20    bool isPrime(int n) {
21        // Numbers less than 2 are not prime
22        if (n < 2) {
23            return false;
24        }
25      
26        // Check divisibility from 2 up to the square root of n
27        for (int i = 2; i * i <= n; ++i) {
28            if (n % i == 0) {
29                return false; // n is not prime if divisible by i
30            }
31        }
32        return true; // n is prime
33    }
34};
35

1// Function to find the maximum difference between the indices of prime numbers in an array
2function maximumPrimeDifference(nums: number[]): number {
3  
4    // Helper function to determine if a number is prime
5    const isPrime = (x: number): boolean => {
6        if (x < 2) {
7            return false; // Numbers less than 2 are not prime
8        }
9      
10        // Check divisibility from 2 up to the square root of x
11        for (let i = 2; i <= Math.sqrt(x); i++) {
12            if (x % i === 0) {
13                return false; // x is divisible by i, thus not prime
14            }
15        }
16      
17        return true; // x is prime
18    };
19
20    // Iterate from the beginning of the array to find the first prime
21    for (let i = 0; ; ++i) {
22        if (isPrime(nums[i])) {
23
24            // Iterate from the end of the array to find the last prime
25            for (let j = nums.length - 1; ; --j) {
26                if (isPrime(nums[j])) {
27                    return j - i; // Return the difference in indices
28                }
29            }
30        }
31    }
32}
33

Time and Space Complexity

The time complexity of the code is O(n \times \sqrt{M}), where n is the length of the array nums, and M is the maximum value in the array nums. This is because is_prime is called for each element in nums, and checking if a number x is prime involves iterating up to sqrt(x). As x can be as large as M, the complexity of each prime check is O(\sqrt{M}), resulting in the overall time complexity being O(n \times \sqrt{M}).

The space complexity is O(1) because the function uses a constant amount of extra space. The space used does not scale with the input size; only fixed-size variables are allocated.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know