two pointers
The two-pointers technique uses two indices that move through a sequence in a coordinated way, so that work which would naively take a nested loop collapses into a single pass. Rather than comparing every pair of positions, you keep two markers and advance one or the other according to what you see — turning many O(n^2) problems into O(n). It is one of the most reliably useful patterns on arrays and strings, and it leans heavily on the data being sorted (or otherwise monotone), because that order is what tells you which pointer to move.
There are two common shapes. Converging pointers start at the two ends and walk toward each other: to test whether a sorted array holds two numbers summing to a target, put one pointer at the front and one at the back, and at each step compare their sum to the target — too small, advance the left pointer to grow the sum; too large, retreat the right pointer to shrink it; equal, you've found the pair. Because each step moves a pointer inward and they never cross back, the whole scan is O(n). The same idea reverses an array in place or checks for a palindrome.
The other shape is independent (often fast/slow) pointers travelling the same direction at different speeds: a slow pointer that marks where the next kept element goes and a fast pointer that scans ahead is the classic way to remove duplicates from a sorted array or filter in place. In linked lists, a pointer that moves two steps for every one of another detects a cycle (Floyd's tortoise-and-hare) and finds the middle node. The unifying idea is that the two pointers together encode a state you advance cleverly — never re-examining what a single pass has already settled — giving O(n) time and O(1) extra space.
bool hasPair(const vector<int>& a, int target) {
int lo = 0, hi = a.size() - 1; // sorted input required
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return true;
if (s < target) ++lo; // too small: grow the sum
else --hi; // too large: shrink the sum
}
return false; // O(n) time, O(1) space
}Each step moves exactly one pointer inward, so the scan is O(n) on sorted input.
Two pointers usually relies on the input being sorted — that order is exactly what tells you which pointer to move next. On unsorted data you may need to sort first (an extra O(n log n)) or reach for a hash table instead. The sliding-window pattern is a close cousin: a window bounded by a left and a right pointer.