Pair Sum is N

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

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.

bool pairSum(int n, Array numbers) {
  Set set

  if (numbers.length < 2)
    return false

  set.put(numbers[0])
  
  for (i = 1; i < numbers.length; i++) {
    int m = numbers[i]
    int difference = n - m

    if (set.contains(difference))
      return true

    set.put(m)
  }

  return false
}