Two pointer technique: Definition & Examples

The two pointer technique uses two indices that move through one or more sequences. Each move follows a rule that lets the algorithm discard candidates or update a result without revisiting earlier positions. In cash reconciliation, the opposite-end version can find two ledger adjustments that add to a known difference in one pass over an array sorted by amount.

Finding two entries that explain an 11-cent difference

A fictional ledger has five candidate adjustments of 1, 3, 4, 7 and 9 cents. Start with 1 and 9. Their sum is 10, so even the largest possible partner for 1 falls short. Drop 1. Now 3 plus 9 is 12, so even the smallest remaining partner for 9 overshoots. Drop 9. Next, 3 plus 7 is 10, so drop 3. The remaining check, 4 plus 7, gives the target of 11 cents.

Of ten pairs in the fictional ledger, the scan checks sums of 10, 12, 10 and 11 cents in order. The match is 4 plus 7 cents. Six other pairs are ruled out without checking.

Each row fixes the left amount and each column fixes the right amount. A failed check rules out all still-eligible pairs in that row or column.

What makes an endpoint safe to drop

Let

a_i

and

a_j

be the current endpoints of an ascending array, with

i<j

and target

T

. The invariant is that both records of every possible match are still within the current bounds. It holds at the start, when the bounds cover the whole array.

If $a_i+a_j<T$ , every eligible partner $a_k$ for the left record has $a_k\le a_j$ . The left record cannot reach $T$ , so advance $i$ .
If $a_i+a_j>T$ , every eligible partner $a_k$ for the right record has $a_k\ge a_i$ . The right record already overshoots with the smallest eligible partner, so decrement $j$ .
If $a_i+a_j=T$ , return the two records. If the indices meet first, the remaining range has fewer than two records.

The bounds use sorted order, so signed adjustments and repeated amounts work too. Preserve the row ID alongside each amount when sorting. A target of 10 cents can use two 5-cent entries with different IDs, while a single 5-cent entry cannot fill both positions. An exact amount match identifies a candidate for reconciliation. Date, account or currency restrictions must be enforced separately. University of Northern Iowa, “Solving Pairwise Sums”

Count the sort when the input is unsorted

Each failed check shrinks the gap between the indices by one. The scan takes

O(n)

time and

O(1)

auxiliary space on an already sorted array of

n

records. For unsorted input, an

O(n\log n)

sort followed by the scan takes

O(n\log n)

time in total. Extra space depends on the sort and whether you make a separate array of amounts and IDs. The SelfMadeQuant mergesort example derives the sorting cost from its linear merge step (public preview, full lesson for members).

A sliding window is another two-pointer pattern. Its boundaries move forward through the sequence, and the observations between them contribute to a contiguous interval, such as a recent total in timestamp order. The opposite-end search moves inward and sums only the two endpoints of the remaining candidate range. Purdue University, Week 2 course notes

Finding two entries that explain an 11-cent difference

What makes an endpoint safe to drop

Count the sort when the input is unsorted

Sources

Related terms

Array

Sliding window algorithm