Two pointers: pair sum

Find two values in a sorted array that add up to a target by closing in from both ends.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Because the array is sorted, moving the left pointer right can only increase the sum and moving the right pointer left can only decrease it. One pass replaces the O(n²) check of every pair.

Code

C++PythonC#

pair<int, int> pairSum(const vector<int>& a, int target) {
    int l = 0, r = (int)a.size() - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == target) return {l, r};
        if (sum < target) l++;
        else r--;
    }
    return {-1, -1};
}

def pair_sum(a: list[int], target: int) -> tuple[int, int] | None:
    l, r = 0, len(a) - 1
    while l < r:
        total = a[l] + a[r]
        if total == target: return (l, r)
        if total < target: l += 1
        else: r -= 1
    return None

public static (int, int)? PairSum(int[] a, int target) {
    int l = 0, r = a.Length - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == target) return (l, r);
        if (sum < target) l++;
        else r--;
    }
    return null;
}

Tips

Sum too small: move l. Sum too big: move r.
The same idea powers 3-sum, container with most water, and removing duplicates in place.

In the .NET library

No built-in for this. The (int, int)? return type is a nullable ValueTuple, a tidy way to return "a pair or nothing".