2 sum Optimal

The Two-Pointer Approach: Efficiently Finding a Pair with a Given Sum

The two-pointer approach is a widely used technique for solving problems efficiently, especially when dealing with sorted arrays. In this article, we’ll explore how to use this method to determine if there exists a pair of elements in a sorted array that sum up to a given target.

Understanding the Two-Pointer Approach

The core idea behind this technique is to maintain two pointers:

• Left pointer (left): Starts from the beginning of the array.

• Right pointer (right): Starts from the end of the array.

The algorithm works as follows:

1. Sort the array (if it’s not already sorted).

2. Initialize two pointers: left = 0 and right = n - 1.

3. Check the sum of elements at left and right:

   • If the sum is less than the target, move left forward to increase the sum.

   • If the sum is greater than the target, move right backward to decrease the sum.

   • If the sum matches the target, return true (pair found).

4. Repeat until the pointers meet.

Implementation in C++

Below is the C++ implementation of this approach:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {4, 1, 2, 3, 1};
    int target = 5;
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 1: Sort the array
    sort(arr, arr + n);

    // Step 2: Initialize two pointers
    int left = 0, right = n - 1;

    // Step 3: Apply the two-pointer approach
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum < target) {
            left++;  // Increase sum by moving left pointer forward
        } else if (sum > target) {
            right--; // Decrease sum by moving right pointer backward
        } else {
            cout << "Yes"; // Pair found
            return 0;
        }
    }

    cout << "No"; // No pair found
    return 0;
}

Explanation of the Code

1. Sorting the array: Sorting helps in efficiently checking pairs using the two-pointer technique.

2. Initializing left and right pointers.

3. Iterating while left < right:

   • If arr[left] + arr[right] < target, move left forward.

   • If arr[left] + arr[right] > target, move right backward.

   • If a pair is found, print "Yes" and exit.

4. If the loop completes without finding a pair, print "No".

Why Use the Two-Pointer Approach?

• Time Complexity: O(n log n) (due to sorting) + O(n) (traversal) → O(n log n) in total.

• Space Complexity: O(1) since we use only two additional pointers.

• Optimized for Sorted Arrays: It efficiently finds the required sum without checking all possible pairs.

Example Walkthrough

Consider the input array:

arr[] = {4, 1, 2, 3, 1}, target = 5

Step-by-Step Execution:

1. Sort the array → {1, 1, 2, 3, 4}

2. Initialize pointers → left = 0, right = 4

3. Check pairs:

   • 1 + 4 = 5 → Found!

4. Output: "Yes"

Conclusion

The two-pointer approach is an elegant and efficient method to solve pair sum problems in sorted arrays. It is widely used in problems like:

• Finding pairs with a given sum

• Checking if a triplet exists with a given sum (by extending the approach)

• Solving problems on sorted arrays efficiently

By leveraging this method, you can solve problems with reduced time complexity and optimized performance. Happy coding!