Pair Sum Problem

Given a number N and an array of numbers, determine if any pair of numbers in the array has a sum equal to N.

Approaches

One approach is to sort the array and then do a binary search for the difference of N and the ith element for all i. Sorting is O(n log n) and searching for a pair for all elements is also O(n log n).

A faster approach is to maintain a set of visited elements and determine if the difference of N and the ith element exists in the set. This runs in a single pass of the array, or O(n) time.

Code Implementation

function pairSum(n, numbers) {
  const set = new Set();

if (numbers.length < 2) {
    return false;
  }

set.add(numbers[0]);

for (let i = 1; i < numbers.length; i++) {
    const m = numbers[i];
    const difference = n - m;

if (set.has(difference)) {
      return true;
    }

set.add(m);
  }

return false;
}

This solution efficiently checks if any two numbers in the array can sum up to the given number N.