2523. Closest Prime Numbers in Range

Problem

Given two positive integers left and right, find the two integers num1 and num2 such that:

• left <= nums1 < nums2 <= right .

• nums1 and nums2 are both prime numbers.

• nums2 - nums1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 value or [-1, -1] if such numbers do not exist.

A number greater than 1 is called prime if it is only divisible by 1 and itself.

  Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

  Constraints:

• 1 <= left <= right <= 106

  .spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0;  } .spoiler {overflow:hidden;} .spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;} .spoilerbutton[value="Show Message"] + .spoiler > div {margin-top:-500%;} .spoilerbutton[value="Hide Message"] + .spoiler {padding:5px;}

Solution (Java)

class Solution {
    boolean[] sieveOfEratosthenes(int n) {
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
        for (int p = 2; p * p <= n; p++) {
            if (prime[p] == true) {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        return prime;
    }
    public int[] closestPrimes(int left, int right) {
        var primes = sieveOfEratosthenes(right);  
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        if(left <= 1) left = 2;
        for(int i = left; i <= right; i++) {
            if(primes[i]) pq.add(i);
        }
        if(pq.isEmpty()) return new int[]{-1,-1};
        int l = -1,r = -1,diff = 999999;
        int s1 = pq.poll();
        while(!pq.isEmpty()) {
            int s2 = pq.poll();
            if(s2 - s1 < diff) {
                l = s1;
                r = s2;
                diff = r - l;
            }
            s1 = s2;
        }
        return new int[]{l,r};
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).