The two pointers technique moves two indices through an array (or string) in coordination and replaces nested loops (O(n^2)) with one pass (O(n)). There are two main forms: opposing and fast/slow.

![Pointer moves in [1, 3, 4, 6, 8, 11] for target 10](img/lessons/algorithms/two-pointers-pair-sum-trace.svg)

Opposing pointers: a pair with a given sum

In a sorted array we start with i = 0 and j = n - 1. If the sum a[i] + a[j] is below the target, a[i] cannot form a pair with any a[k] (k <= j), since all of them are at most a[j]; so i can be discarded. If it is above, we discard j symmetrically. This invariant guarantees correctness: the members of a valid pair always lie in [i, j].

python
def pair_sum(a, target):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == target:
            return (i, j)
        if s < target:
            i += 1              # need a bigger sum
        else:
            j -= 1              # need a smaller sum
    return None

data = [1, 3, 4, 6, 8, 11]
print(pair_sum(data, 10))
print(pair_sum(data, 20))
text
(2, 3)
None