Finding Pair with Target Sum

Given a sorted array of numbers and a target sum, find the pair of numbers that add up to the target sum.

Example:

• Input: [1, 2, 3, 4, 5, 6], Target: 10
• Expected Output: [4, 6] (since 4 + 6 = 10)

Let's explore two approaches to solve this problem: the straightforward brute force method and the more elegant two-pointer technique.

---

Approach 1: Brute Force

The brute force approach is the most intuitive way to solve this problem. We'll check every possible pair of numbers in the array and see if they add up to the target sum.

The Algorithm

1. Use two nested loops to consider every possible pair
2. For each pair, check if their sum equals the target
3. Return the pair when found

Implementation

function findPairBruteForce(arr, targetSum) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === targetSum) {
        return [arr[i], arr[j]];
      }
    }
  }
  return []; // No pair found
}

// Test
const nums = [1, 2, 3, 4, 5, 6];
const target = 10;
console.log(findPairBruteForce(nums, target)); // Output: [4, 6]

Time and Space Complexity

• Time Complexity: O(n²) - We're using two nested loops, each potentially iterating through the entire array.
• Space Complexity: O(1) - We only use a constant amount of extra space.

While this approach works correctly, it's not efficient for large input arrays. Can we do better? Yes, we can!

---

Approach 2: Two-Pointer Technique

Since our array is sorted, we can use a more efficient approach called the "two-pointer technique." This method takes advantage of the sorted nature of the array to find the pair in a single pass.

The Algorithm

1. Initialize two pointers: left at the beginning of the array and right at the end
2. Calculate the sum of elements at these pointers
3. If the sum equals the target, we've found our pair
4. If the sum is greater than the target, decrement the right pointer (to reduce the sum)
5. If the sum is less than the target, increment the left pointer (to increase the sum)
6. Repeat until we find the pair or the pointers meet

Implementation

function findPairTwoPointer(arr, targetSum) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const currentSum = arr[left] + arr[right];

    if (currentSum === targetSum) {
      return [arr[left], arr[right]];
    }

    if (currentSum < targetSum) {
      left++; // Need a larger sum, move left pointer right
    } else {
      right--; // Need a smaller sum, move right pointer left
    }
  }

  return []; // No pair found
}

// Test
const nums = [1, 2, 3, 4, 5, 6];
const target = 10;
console.log(findPairTwoPointer(nums, target)); // Output: [4, 6]

Time and Space Complexity

• Time Complexity: O(n) - We're making a single pass through the array.
• Space Complexity: O(1) - We only use a constant amount of extra space.

---

Visual Explanation

Let's see how the two-pointer approach works with our example:

1. Initial state: left = 0 (value 1), right = 5 (value 6)

   • Sum = 1 + 6 = 7 (less than target 10)
   • Move left pointer right

2. Next state: left = 1 (value 2), right = 5 (value 6)

   • Sum = 2 + 6 = 8 (less than target 10)
   • Move left pointer right

3. Next state: left = 2 (value 3), right = 5 (value 6)

   • Sum = 3 + 6 = 9 (less than target 10)
   • Move left pointer right

4. Next state: left = 3 (value 4), right = 5 (value 6)

   • Sum = 4 + 6 = 10 (equals target 10)
   • Pair found: [4, 6]

---

What About Unsorted Arrays?

So far, we've been working with sorted arrays, which allowed us to use the efficient two-pointer approach. But what if our input array isn't sorted?

Option 1: Sort First, Then Apply Two-Pointer

We could sort the array first and then apply the two-pointer technique:

function findPairUnsortedArray(arr, targetSum) {
  // Sort the array
  const sortedArr = [...arr].sort((a, b) => a - b);

  // Apply two-pointer technique on sorted array
  let left = 0;
  let right = sortedArr.length - 1;

  while (left < right) {
    const currentSum = sortedArr[left] + sortedArr[right];

    if (currentSum === targetSum) {
      // Found the pair
      return [sortedArr[left], sortedArr[right]];
    }

    if (currentSum < targetSum) {
      left++;
    } else {
      right--;
    }
  }

  return []; // No pair found
}

// Test with unsorted array
const unsortedNums = [6, 3, 5, 2, 1, 4];
const target = 10;
console.log(findPairUnsortedArray(unsortedNums, target)); // Output: [4, 6]

Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) for the copied array

Option 2: Use a Hash Set (Most Efficient for Unsorted Arrays)

For unsorted arrays, a hash set approach is often the most efficient:

function findPairHashSet(arr, targetSum) {
  const seen = new Set();

  for (let i = 0; i < arr.length; i++) {
    const currentNum = arr[i];
    const complement = targetSum - currentNum;

    if (seen.has(complement)) {
      return [complement, currentNum];
    }

    seen.add(currentNum);
  }

  return []; // No pair found
}

// Test with unsorted array
const unsortedNums = [6, 3, 5, 2, 1, 4];
const target = 10;
console.log(findPairHashSet(unsortedNums, target)); // Output: [4, 6]

Time Complexity: O(n) - We're making a single pass through the array.
Space Complexity: O(n) - In the worst case, we might end up storing all numbers in the hash set.

This hash set approach is optimal for unsorted arrays as it maintains O(n) time complexity without requiring sorting. The method works by storing each number we've seen in a Set and checking if the complement (target sum - current number) exists in our set.

---

Comparing All Approaches

Let's compare all our approaches:

Approach	Time Complexity	Space Complexity	Works with Unsorted Arrays?
Brute Force	O(n²)	O(1)	Yes
Two-Pointer	O(n)	O(1)	No (requires sorted array)
Sort + Two-Pointer	O(n log n)	O(n)	Yes (sorts first)
Hash Set	O(n)	O(n)	Yes

---

Final Thoughts

The two-pointer technique demonstrates how understanding the properties of your input (in this case, a sorted array) can lead to much more efficient solutions. For unsorted arrays, the hash set approach offers the best performance.

This problem illustrates an important principle in algorithm design: always consider the properties of your input data when selecting an algorithm. While the brute force approach is always a good starting point, identifying opportunities to optimize is what separates good programmers from great ones.

Next time you encounter a problem involving pairs of elements that need to satisfy a condition together, consider whether the two-pointer technique or hash set approach might help!

Happy coding! 💻✨