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

Solution

Method 1 - Using Sieve of Eratosthenes

Key Observations:
- Prime numbers are greater than 1 and only divisible by 1 and themselves.
- To minimise the difference num2 - num1, we need all prime numbers in the range [left, right] to check consecutive pairs.
Steps to Solve:
- Prime Generation (Sieve of Eratosthenes):
  - Use an efficient sieve-based approach to mark primes up to right because generating primes up to right ensures all candidates between left and right.
- Filter primes within [left, right] from the sieve result.
- Iterate through the filtered primes to find pairs with the minimum difference num2 - num1.
Edge Case:
- If there are fewer than 2 primes between left and right, directly return [-1, -1].

Code

[{"language":"Java","code":"class Solution {\n    public int[] closestPrimes(int left, int right) {\n        // Step 1: Generate all primes up to `right` using the Sieve of Eratosthenes\n        boolean[] isPrime = new boolean[right + 1];\n        for (int i = 2; i <= right; i++) {\n            isPrime[i] = true;\n        }\n        for (int i = 2; i * i <= right; i++) {\n            if (isPrime[i]) {\n                for (int j = i * i; j <= right; j += i) {\n                    isPrime[j] = false;\n                }\n            }\n        }\n\n        // Step 2: Filter primes within the range [left, right]\n        List<Integer> primesInRange = new ArrayList<>();\n        for (int i = Math.max(left, 2); i <= right; i++) {\n            if (isPrime[i]) {\n                primesInRange.add(i);\n            }\n        }\n        \n        // Step 3: Find the closest primes\n        int[] ans = {-1, -1};\n        int minDiff = Integer.MAX_VALUE;\n        for (int i = 1; i < primesInRange.size(); i++) {\n            int diff = primesInRange.get(i) - primesInRange.get(i - 1);\n            if (diff < minDiff) {\n                minDiff = diff;\n                ans[0] = primesInRange.get(i - 1);\n                ans[1] = primesInRange.get(i);\n            }\n        }\n        \n        return ans;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def closestPrimes(self, left: int, right: int) -> List[int]:\n        # Step 1: Generate all primes up to `right` using the Sieve of Eratosthenes\n        is_prime = [True] * (right + 1)\n        is_prime[0] = is_prime[1] = False  # 0 and 1 are not primes\n        \n        for i in range(2, int(right**0.5) + 1):\n            if is_prime[i]:\n                for j in range(i * i, right + 1, i):\n                    is_prime[j] = False\n        \n        # Step 2: Filter primes within the range [left, right]\n        primes_in_range = [i for i in range(max(left, 2), right + 1) if is_prime[i]]\n        \n        # Step 3: Find the closest primes\n        ans = [-1, -1]\n        min_diff = float('inf')\n        for i in range(1, len(primes_in_range)):\n            diff = primes_in_range[i] - primes_in_range[i - 1]\n            if diff < min_diff:\n                min_diff = diff\n                ans = [primes_in_range[i - 1], primes_in_range[i]]\n        \n        return ans","lang":"python"}]

Complexity

⏰ Time complexity: O(r log log r)
- Sieve of Eratosthenes: O(n log log n) for n = right.
- Filtering primes within [left, right]: O(r - l) where r = right and l = left.
- Pair iteration to find the closest primes: O(p) for p pr

Related Tags