Two Pointers (Pair Sum) Algorithm Tutorial

Two Pointers Technique

The Two Pointers technique uses two indices moving through a data structure to solve problems efficiently. For sorted arrays, you often use one pointer at each end moving toward the center.

To find a pair with a target sum in a sorted array, you compare the sum at both pointers with the target.

function twoSum(arr, n, target):
    left = 0
    right = n - 1

    while left < right:
        sum = arr[left] + arr[right]
        if sum == target:
            return (left, right)
        else if sum < target:
            left = left + 1
        else:
            right = right - 1

    return (-1, -1)

Why it works: In a sorted array, if the current sum is too small, you need a larger value. The only way to get a larger sum is to move the left pointer right. Similarly, if the sum is too large, you move the right pointer left.

Counting pairs: To count all pairs with a given sum, you handle duplicates by counting occurrences when pointers meet.

Applications: You use two pointers for pair sum problems, container with most water, removing duplicates, merging sorted arrays, and palindrome checking.

Time complexity: $O(n)$ because each pointer moves at most $n$ times.

Space complexity: $O(1)$ using only two index variables.