Find a Pair with a Given Sum

A naive brute-force solution with two nested loops would have a quadratic complexity of O(n²), which does not meet the requirement. To achieve linear complexity O(n), you need to avoid nested loops.

Think about how you can remember the numbers you have already seen. For each new number, how can you quickly check if you have previously encountered its “complement” to reach the desired sum? What data structure allows you to check for the existence of an element in constant time O(1)?

const hasPairWithSum = (arr, sum) => {
  // Create a Set to store the numbers we have already seen.
  // A Set provides very fast lookups (on average O(1)).
  const seenNumbers = new Set();
 
  // Iterate through each number in the input array.
  for (const num of arr) {
    // For each number `num`, calculate the "complement",
    // which is the number that, when added to `num`, gives `sum`.
    const complement = sum - num;
 
    // Check if this "complement" exists in our Set.
    // If it does, we have found a pair.
    if (seenNumbers.has(complement)) {
      return true; // Pair found, exit the function immediately.
    }
 
    // If the "complement" is not found, add the current number `num` to the Set.
    // This is so that subsequent numbers can find it as their complement.
    seenNumbers.add(num);
  }
 
  // If we have iterated through the entire array and haven't found a pair,
  // it means one does not exist. Return false.
  return false;
};

Why it works:

• Linear Complexity O(n): We iterate through the array only once.
• Set for Speed: The add and has operations in a Set have an average time complexity of O(1). This allows us to instantly check for each element if we have already seen the number that would sum up with the current one to sum.
• Logic: For each number num in the array, we calculate the complement needed to make the sum. Then, we check if this complement is in our Set. If it is, we’ve found a pair and can return true. If not, we add the current number num to the Set and move to the next element. If we get through the whole array without finding a pair, we return false.
• Space Complexity: O(n) in the worst case, as the Set might store all elements of the array.

const hasPairWithSum = (arr, sum) => {
  // Sort the array. Complexity: O(n log n)
  const sortedArr = [...arr].sort((a, b) => a - b);
  
  let left = 0;
  let right = sortedArr.length - 1;
 
  // Iterate through the array from both ends. Complexity: O(n)
  while (left < right) {
    const currentSum = sortedArr[left] + sortedArr[right];
 
    if (currentSum === sum) {
      return true; // Found a pair
    } else if (currentSum < sum) {
      left++; // The sum is too small, move the left pointer to the right
    } else {
      right--; // The sum is too large, move the right pointer to the left
    }
  }
 
  return false; // Pair not found
};

Why it works:

• Idea: If the array is sorted, you can efficiently check sums by moving from both ends towards each other.
• Time Complexity O(n log n): This is mainly determined by the sorting step. The pointer traversal itself is linear (O(n)), but sorting takes more time. This solution does not meet the strict O(n) requirement but is a classic approach to the problem.
• Space Complexity O(1) or O(log n): If you modify the original array (arr.sort()), almost no extra memory is needed (depends on the sort implementation). In the example, we create a copy, which results in O(n), but this can be optimized.
• Trade-off: This method is good when you cannot use extra memory (as in Solution #1) and a complexity of O(n log n) is acceptable.