The Two-Pointers Technique: Sweep Arrays in O(n)

The two-pointers technique uses two indices that move through an array in a coordinated way, letting you solve in a single O(n) pass problems that look like they need a nested O(n²) loop. It shines on sorted arrays and on in-place rearrangement, and it comes in two flavours: pointers starting at opposite ends and moving inward, or two pointers moving in the same direction at different speeds.

Flavour 1: opposite ends (converging)

Start one pointer at the left, one at the right, and move them toward each other based on a comparison. The classic use is pair-sum on a sorted array: find two numbers that add up to a target.

The insight: if a[lo] + a[hi] is too small, the only way to increase the sum is to move lo right (a bigger small number); if it’s too big, move hi left. Each step rules out a whole row/column of the brute-force pair grid.

// sorted a: return indices of a pair summing to target, or {-1,-1}
std::pair<int,int> pairSum(const std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int s = a[lo] + a[hi];
        if (s == target) return {lo, hi};
        else if (s < target) lo++;   // need a larger sum
        else hi--;                    // need a smaller sum
    }
    return {-1, -1};
}

// sorted a: return indices of a pair summing to target, or [-1,-1]
int[] pairSum(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int s = a[lo] + a[hi];
        if (s == target) return new int[]{lo, hi};
        else if (s < target) lo++;   // need a larger sum
        else hi--;                    // need a smaller sum
    }
    return new int[]{-1, -1};
}

// sorted a: return indices of a pair summing to target, or [-1,-1]
function pairSum(a, target) {
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    const s = a[lo] + a[hi];
    if (s === target) return [lo, hi];
    else if (s < target) lo++;   // need a larger sum
    else hi--;                    // need a smaller sum
  }
  return [-1, -1];
}

# sorted a: return indices of a pair summing to target, or (-1,-1)
def pair_sum(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1          # need a larger sum
        else:
            hi -= 1          # need a smaller sum
    return (-1, -1)

Flavour 2: same direction (slow + fast)

Both pointers start at the left. A fast pointer scans ahead reading data; a slow (write) pointer marks where the next kept element goes. This is the engine behind in-place filtering. Here we remove duplicates from a sorted array in place, returning the new length:

int dedupeSorted(std::vector<int>& a) {
    if (a.empty()) return 0;
    int slow = 0;                          // last unique slot
    for (int fast = 1; fast < (int)a.size(); fast++)
        if (a[fast] != a[slow])
            a[++slow] = a[fast];
    return slow + 1;                       // length of unique prefix
}

int dedupeSorted(int[] a) {
    if (a.length == 0) return 0;
    int slow = 0;                          // last unique slot
    for (int fast = 1; fast < a.length; fast++)
        if (a[fast] != a[slow])
            a[++slow] = a[fast];
    return slow + 1;                       // length of unique prefix
}

function dedupeSorted(a) {
  if (a.length === 0) return 0;
  let slow = 0;                          // last unique slot
  for (let fast = 1; fast < a.length; fast++)
    if (a[fast] !== a[slow])
      a[++slow] = a[fast];
  return slow + 1;                       // length of unique prefix
}

def dedupe_sorted(a):
    if not a:
        return 0
    slow = 0                              # last unique slot
    for fast in range(1, len(a)):
        if a[fast] != a[slow]:
            slow += 1
            a[slow] = a[fast]
    return slow + 1                       # length of unique prefix

Why it’s fast

Each pointer only ever moves forward (or the two only ever move toward each other), so together they take at most n steps. That’s O(n) time and O(1) extra space — a clean win over the O(n²) brute force for pairs.

For beginners: The trick that makes opposite-ends work is order. On an unsorted array, knowing the sum is “too small” tells you nothing about which pointer to move. Sort first (O(n log n)) if the problem allows it.

When to reach for two pointers

A sorted array and you need pairs/triples with a sum or difference property.
In-place rearrangement: remove/move elements without extra arrays (dedupe, move zeros, partition).
Comparing two sequences in lockstep (e.g. merging two sorted arrays).
A close cousin, fast & slow pointers, detects cycles and finds midpoints in linked lists.

Going deeper: This page is the searching-section primer. For the full pattern — recognizing it across many problem shapes, with a decision checklist — see the two-pointers pattern. It also sets up the closely related sliding window, which is two same-direction pointers maintaining a window.

Next: search a range of answers with binary search on the answer, or practice on the searching exercises.