LeetCode 2523 - Closest Prime Numbers in Range

LeetCode Problem 2523

Difficulty: 🟡 Medium
Topics: Math, Number Theory

Solution

Problem Understanding

The problem asks us to find two prime numbers inside a given inclusive range [left, right] such that the difference between them is as small as possible.

More formally, we need to return two integers [num1, num2] where:

• left <= num1 < num2 <= right
• Both numbers are prime
• The gap num2 - num1 is minimized among all valid prime pairs

If multiple pairs have the same smallest gap, we return the pair with the smaller first number. Since we naturally scan numbers in increasing order, the first minimum gap pair we encounter automatically satisfies this requirement.

The input consists of two integers:

• left, the lower bound of the range
• right, the upper bound of the range

The output is:

• A two-element array containing the closest pair of primes
• [-1, -1] if fewer than two primes exist in the range

The constraints are important:

• 1 <= left <= right <= 10^6

A range up to one million is too large for repeated expensive primality testing on every number using naive trial division. We need a more efficient way to generate primes.

Several edge cases are important:

• The range may contain fewer than two primes, for example [4, 6]
• The range may start below the first prime number, such as [1, 10]
• Multiple prime pairs may have the same minimum gap
• Consecutive twin primes may exist, producing the smallest possible gap of 2
• The range may be very large, requiring efficient preprocessing

The problem guarantees valid integer bounds and that left <= right.

Approaches

Brute Force Approach

A straightforward solution is to iterate through every number in the range and test whether it is prime using trial division.

For each number x, we check divisibility from 2 through sqrt(x). If no divisor exists, the number is prime. After collecting all primes in the range, we scan adjacent pairs and compute their differences to find the minimum gap.

This approach is correct because:

1. Every number in the range is checked
2. Every prime is collected
3. Every adjacent prime pair is examined
4. The minimum gap among adjacent primes is necessarily the global minimum

However, this solution becomes expensive for large ranges. In the worst case, we may perform primality testing for nearly one million numbers, each requiring up to O(sqrt(n)) operations.

Optimal Approach, Sieve of Eratosthenes

The key observation is that we need prime information for many numbers in a contiguous range. Instead of testing each number independently, we can preprocess all primes up to right using the Sieve of Eratosthenes.

The sieve works by:

1. Initially assuming all numbers are prime
2. Iteratively marking multiples of each prime as composite
3. Leaving only true prime numbers unmarked

This allows us to determine primality for every number up to 10^6 in near linear time.

Once we have the sieve:

• Iterate through [left, right]
• Track the previous prime encountered
• Compute gaps between consecutive primes
• Update the best answer whenever a smaller gap is found

Since prime gaps are minimized between consecutive primes, checking adjacent primes is sufficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((right - left + 1) * sqrt(right))	O(k)	Tests each number independently for primality
Optimal	O(right log log right)	O(right)	Uses Sieve of Eratosthenes for efficient preprocessing

Here, k is the number of primes in the range.

Algorithm Walkthrough

Optimal Algorithm

1. Create a boolean array is_prime of size right + 1.

Each index represents whether the number is prime. Initially, assume every number is prime except 0 and 1. 2. Run the Sieve of Eratosthenes.

Start from 2. For every number that is still marked prime, mark all of its multiples as non-prime.

We only need to iterate up to sqrt(right) because larger composite numbers will already have smaller factors. 3. Initialize tracking variables.

Maintain:

• previous_prime, the last prime encountered
• best_pair, the current answer
• minimum_gap, the smallest difference found so far

4. Iterate through all numbers from left to right.

For each number:

• If it is not prime, skip it

• Otherwise:

• If previous_prime exists, compute the gap

• Compare the gap against minimum_gap

• Update the answer if the gap is smaller

• Store the current prime as previous_prime

5. Return the result.

If no valid pair was found, return [-1, -1].

Why it works

The Sieve of Eratosthenes correctly identifies all prime numbers up to right. Once the primes are known, the minimum prime gap must occur between two consecutive primes in sorted order. Any non-consecutive pair would necessarily have a larger or equal difference because another prime lies between them. Therefore, scanning adjacent primes guarantees that we find the globally minimum gap pair.

Python Solution

from typing import List

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        is_prime = [True] * (right + 1)

        if right >= 0:
            is_prime[0] = False
        if right >= 1:
            is_prime[1] = False

        limit = int(right ** 0.5)

        for num in range(2, limit + 1):
            if is_prime[num]:
                for multiple in range(num * num, right + 1, num):
                    is_prime[multiple] = False

        previous_prime = -1
        minimum_gap = float("inf")
        answer = [-1, -1]

        for num in range(left, right + 1):
            if not is_prime[num]:
                continue

            if previous_prime != -1:
                gap = num - previous_prime

                if gap < minimum_gap:
                    minimum_gap = gap
                    answer = [previous_prime, num]

            previous_prime = num

        return answer

The implementation begins by constructing the is_prime array. Every number is initially assumed to be prime. We immediately mark 0 and 1 as non-prime because they do not satisfy the mathematical definition of prime numbers.

Next, the sieve phase begins. For every prime number num, we mark all multiples starting from num * num as composite. Starting at num * num is an optimization because smaller multiples would already have been processed by smaller prime factors.

After preprocessing, we scan the target range from left to right.

The variable previous_prime stores the most recent prime encountered. Whenever we discover another prime, we compute the difference between the two consecutive primes.

If this difference is smaller than the current best gap, we update the answer.

Finally, if no valid pair exists, the default [-1, -1] is returned.

Go Solution

func closestPrimes(left int, right int) []int {
    isPrime := make([]bool, right+1)

    for i := 0; i <= right; i++ {
        isPrime[i] = true
    }

    if right >= 0 {
        isPrime[0] = false
    }

    if right >= 1 {
        isPrime[1] = false
    }

    for num := 2; num*num <= right; num++ {
        if isPrime[num] {
            for multiple := num * num; multiple <= right; multiple += num {
                isPrime[multiple] = false
            }
        }
    }

    previousPrime := -1
    minimumGap := int(^uint(0) >> 1)
    answer := []int{-1, -1}

    for num := left; num <= right; num++ {
        if !isPrime[num] {
            continue
        }

        if previousPrime != -1 {
            gap := num - previousPrime

            if gap < minimumGap {
                minimumGap = gap
                answer[0] = previousPrime
                answer[1] = num
            }
        }

        previousPrime = num
    }

    return answer
}

The Go implementation follows the same algorithmic structure as the Python solution.

A boolean slice is used for the sieve array. Since Go does not provide a built-in infinity constant for integers, the maximum integer value is computed using bit manipulation:

int(^uint(0) >> 1)

Slices are used for the return value because LeetCode expects []int.

Unlike Python, Go requires explicit initialization of the boolean slice to true.

Worked Examples

Example 1

Input:

left = 10
right = 19

Step 1: Generate primes up to 19

The sieve identifies:

Number	Prime?
10	No
11	Yes
12	No
13	Yes
14	No
15	No
16	No
17	Yes
18	No
19	Yes

Prime list:

[11, 13, 17, 19]

Step 2: Scan consecutive primes

Current Prime	Previous Prime	Gap	Best Pair
11	-1	-	[-1, -1]
13	11	2	[11, 13]
17	13	4	[11, 13]
19	17	2	[11, 13]

The minimum gap is 2.

Although [17, 19] also has gap 2, [11, 13] is returned because it appears first.

Final answer:

[11, 13]

Example 2

Input:

left = 4
right = 6

Step 1: Generate primes

Number	Prime?
4	No
5	Yes
6	No

Only one prime exists.

Step 2: Scan primes

Current Prime	Previous Prime	Gap	Best Pair
5	-1	-	[-1, -1]

No pair can be formed.

Final answer:

[-1, -1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(right log log right)	Sieve preprocessing dominates runtime
Space	O(right)	Boolean array stores primality for each number

The Sieve of Eratosthenes runs in O(n log log n) time, which is significantly faster than repeated primality testing. The second pass through the range is linear and does not change the asymptotic complexity.

The space complexity comes from storing the is_prime array of size right + 1.

Test Cases

solution = Solution()

assert solution.closestPrimes(10, 19) == [11, 13]  # Example case with multiple minimum gaps
assert solution.closestPrimes(4, 6) == [-1, -1]  # Only one prime in range
assert solution.closestPrimes(1, 2) == [-1, -1]  # Single prime at boundary
assert solution.closestPrimes(2, 3) == [2, 3]  # Smallest valid prime pair
assert solution.closestPrimes(14, 16) == [-1, -1]  # No primes in range
assert solution.closestPrimes(1, 10) == [2, 3]  # Range starting below first prime
assert solution.closestPrimes(17, 19) == [17, 19]  # Exactly two primes
assert solution.closestPrimes(100, 120) == [101, 103]  # Larger range
assert solution.closestPrimes(999900, 1000000) == [999959, 999961]  # Stress test near upper bound
assert solution.closestPrimes(3, 5) == [3, 5]  # Two primes with gap 2

Test	Why
[10, 19]	Validates normal operation with multiple optimal pairs
[4, 6]	Validates insufficient prime count
[1, 2]	Tests lower boundary handling
[2, 3]	Smallest possible valid answer
[14, 16]	Tests range with no primes
[1, 10]	Ensures correct handling below first prime
[17, 19]	Tests range with exactly two primes
[100, 120]	Validates larger interval behavior
[999900, 1000000]	Stress tests performance near constraint limit
[3, 5]	Verifies consecutive small primes

Edge Cases

Range Contains Fewer Than Two Primes

A common source of bugs is assuming at least two primes exist in the range. For example, [4, 6] contains only the prime 5.

The implementation handles this by initializing the answer to [-1, -1] and only updating it after finding two primes.

Range Starts Below 2

Numbers 0 and 1 are not prime, but careless implementations sometimes incorrectly classify them as prime.

The sieve explicitly marks:

is_prime[0] = False
is_prime[1] = False

This ensures ranges such as [1, 10] behave correctly.

Multiple Pairs Share the Same Minimum Gap

The problem requires returning the pair with the smaller first value when multiple pairs have the same gap.

For example:

[11, 13] and [17, 19]

both have gap 2.

The implementation updates the answer only when a strictly smaller gap is found:

if gap < minimum_gap:

This preserves the first minimum-gap pair encountered.

No Primes Exist in the Range

Some intervals contain no primes at all, such as [14, 16].

The scan never updates the answer, so the function correctly returns:

[-1, -1]