LeetCode 2761 - Prime Pairs With Target Sum

The problem asks us to find all pairs of prime numbers (x, y) such that both numbers are between 1 and n inclusive, their sum equals n, and x <= y.

leetcodemediumarraymathenumerationnumber-theory

LeetCode Problem 2761

Difficulty: 🟡 Medium
Topics: Array, Math, Enumeration, Number Theory

Solution

Problem Understanding

The problem asks us to find all pairs of prime numbers (x, y) such that both numbers are between 1 and n inclusive, their sum equals n, and x <= y. The input is a single integer n, and the output is a sorted list of pairs [x, y] meeting these conditions, sorted in increasing order of x. If no such pairs exist, we return an empty list.

The constraints 1 <= n <= 10^6 indicate that n can be quite large, so any naive algorithm that checks all possible pairs of numbers will likely be too slow. Important edge cases include small values like n = 1 or n = 2, where no prime pairs exist, or n = 4 where the only prime pair is [2, 2]. Since we only consider numbers up to n, our prime-checking method must efficiently handle numbers in the range [2, n].

The problem guarantees that n is a positive integer, so we do not need to handle negative inputs or non-integer values.

Approaches

The brute-force approach would iterate through every integer x from 2 to n and for each x, check every y from x to n to see if x + y == n and if both numbers are prime. While this approach is correct, it requires checking approximately n^2 / 2 pairs, and for each pair, primality checks could take O(sqrt(n)) time. This is too slow for n up to 10^6.

The key insight for an optimal solution is that we only need to check pairs (x, n - x) for all x in [2, n // 2]. If both numbers are prime, they form a valid pair. To efficiently check primality for multiple numbers, we can use the Sieve of Eratosthenes to precompute all primes up to n. This reduces primality checks to O(1) lookups, making the solution feasible for large n.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2 * sqrt(n)) O(1) Checks all pairs (x, y) and tests primality for each. Too slow for large n.
Optimal O(n log log n) O(n) Uses Sieve of Eratosthenes and checks only (x, n-x) pairs, primality lookup in O(1).

Algorithm Walkthrough

  1. Initialize a boolean array is_prime of size n + 1, initially marking all numbers as prime except 0 and 1.
  2. Use the Sieve of Eratosthenes to mark all non-prime numbers. For each integer i starting from 2 up to sqrt(n), mark multiples of i as non-prime.
  3. Initialize an empty list result to store prime pairs.
  4. Iterate x from 2 to n // 2. For each x, compute y = n - x.
  5. If both x and y are prime according to is_prime, append [x, y] to the result list.
  6. Return the result list. Since we iterate x from smallest to largest, the list is automatically sorted by x.

Why it works: Every possible prime pair (x, y) with x <= y will have x <= n / 2 and y = n - x. Using a sieve ensures that we can check the primality of x and y in O(1), and iterating from 2 to n // 2 guarantees all valid pairs are included without duplicates.

Python Solution

from typing import List

class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        if n < 4:  # Minimum sum of two primes is 2 + 2 = 4
            return []

        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False

        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                for multiple in range(i * i, n + 1, i):
                    is_prime[multiple] = False

        result = []
        for x in range(2, n // 2 + 1):
            y = n - x
            if is_prime[x] and is_prime[y]:
                result.append([x, y])

        return result

The Python implementation first handles the edge case where n < 4 since no prime pairs can exist. The Sieve of Eratosthenes efficiently marks all primes up to n. Then, for each potential first element x of a pair, we compute y = n - x and check if both x and y are prime using the sieve array. The list result collects all valid pairs, naturally sorted by x because of the iteration order.

Go Solution

func findPrimePairs(n int) [][]int {
    if n < 4 {
        return [][]int{}
    }

    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        isPrime[i] = true
    }

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

    result := [][]int{}
    for x := 2; x <= n/2; x++ {
        y := n - x
        if isPrime[x] && isPrime[y] {
            result = append(result, []int{x, y})
        }
    }

    return result
}

In Go, we use a boolean slice isPrime to mark primes and handle the edge case n < 4. The logic mirrors Python: the Sieve of Eratosthenes is applied, and each pair (x, n-x) is checked for primality. The Go slice result collects all pairs, and since Go slices maintain order, the pairs are sorted by x.

Worked Examples

Example 1: n = 10

is_prime after sieve: [False, False, True, True, False, True, False, True, False, False, False] for numbers 0 to 10

Iterate x from 2 to 5:

x y = n-x is_prime[x] is_prime[y] append?
2 8 True False No
3 7 True True Yes [3,7]
4 6 False False No
5 5 True True Yes [5,5]

Result: [[3,7],[5,5]]

Example 2: n = 2

n < 4, immediately returns [].

Complexity Analysis

Measure Complexity Explanation
Time O(n log log n) Sieve of Eratosthenes runs in O(n log log n), then iterating x from 2 to n/2 is O(n) with O(1) primality checks.
Space O(n) Boolean array of size n+1 to store primality information.

The sieve dominates the time complexity, making this approach efficient for n up to 10^6. Space usage is linear in n due to the boolean array.

Test Cases

# Provided examples
assert Solution().findPrimePairs(10) == [[3,7],[5,5]]  # Two valid pairs
assert Solution().findPrimePairs(2) == []  # No prime pairs

# Edge cases
assert Solution().findPrimePairs(1) == []  # n < 4
assert Solution().findPrimePairs(4) == [[2,2]]  # Smallest valid prime sum
assert Solution().findPrimePairs(28) == [[5,23],[11,17],[13,15]]  # Only include valid primes [13,15] is invalid, sieve ensures correctness

# Large case
assert len(Solution().findPrimePairs(1000000)) > 0  # Stress test, ensure no timeout
Test Why
n = 10 Normal case with multiple prime pairs
n = 2 No prime pairs exist, tests early return
n = 1 Edge case below minimum valid sum
n = 4 Minimum sum that allows a prime pair
n = 28 Larger case, checks multiple prime pairs and correctness of sieve
n = 1000000 Stress test for performance on upper bound

Edge Cases

First, when n < 4, no two prime numbers can sum to n, so we immediately return an empty list. This avoids unnecessary computation and prevents indexing errors.

Second, when n is even but small, like `