Find pairs with sum X from a list of numbers

The most efficient approach to find pairs with sum X from a list of numbers is using a hash set (or dictionary in Python). This allows for an average-case time complexity of O(n) by performing a single pass through the list.

Mechanics and Why

For each number num in the input list, we calculate its complement = X - num. We then check if this complement already exists in our seen hash set. If it does, we've found a pair (num, complement) that sums to X. After checking, we add num to the seen hash set. The key advantage of a hash set is its average O(1) time complexity for insertion and lookup operations. This makes the overall process proportional to the number of elements n in the list, hence O(n).

Handling Duplicates and Example

The exact handling of duplicates depends on whether you need to count distinct pairs (e.g., (2,3) and (3,2) are considered the same) or all possible pairs (e.g., from [2,2,3,3] for X=5, you'd count two (2,3) pairs).

For distinct pairs:

def find_distinct_pairs_with_sum(nums, target_sum):
    seen = set()
    found_pairs = set() # Stores unique pairs as sorted tuples
    for num in nums:
        complement = target_sum - num
        if complement in seen:
            # Store sorted tuple to treat (2,3) and (3,2) as the same
            found_pairs.add(tuple(sorted((num, complement))))
        seen.add(num)
    return len(found_pairs) # Or list(found_pairs) if the actual pairs are needed

For counting all possible pairs, including multiple occurrences of the same pair (e.g., [2,2,3,3] for X=5 yields two (2,3) pairs), you would first build a frequency map (like collections.Counter in Python) of all numbers. Then, iterate through the unique numbers in the frequency map:
If num == complement, add count(num) (count(num) - 1) // 2 to the total.
If num != complement, and complement exists in the map, add count(num) count(complement) to the total, ensuring to process each (num, complement) pair only once (e.g., by only considering num < complement).

In the interview, also mention…

For very large datasets that don't fit into memory, this problem shifts from a single-machine O(n) to a distributed computing challenge. In systems like Apache Spark, processing would involve distributing the data. A naive hash set approach would require collecting data to a single node, which is infeasible. Alternatives might include sorting the entire dataset (which involves significant shuffle operations in distributed systems) and then using a two-pointer approach, resulting in O(N log N) overall. Also, consider potential integer overflow if X or num are extremely large in languages with fixed-size integers.