Two Pointers

At a glance

The instinct

Brute force over pairs checks every cell of an n × n grid. Two pointers works when some ordering lets you prove that a whole row or column of that grid is useless after a single comparison. With sorted data and a target sum, if a[i] + a[j] is too small, then pairing a[i] with anything left of j is also too small, so i can advance. One comparison, n candidates eliminated.

There are three common shapes: converging (start at both ends, walk inward), parallel (one pointer per input array, as in merging), and reader/writer (both move forward at different speeds). This guide focuses on the first two; the fast/slow linked-list version is its own pattern.

Recognise it

Not this pattern if...

• The data is unsorted and you must keep original indices: use a hash map (Two Sum) unless sorting is allowed.
• You need the best contiguous window under a constraint: that is Sliding Window (same-direction pointers with a validity rule).
• The pointers walk a linked list to find cycles or midpoints: that is Fast & Slow Pointers.
• You need all pairs, not one best or one matching pair: the output itself may be O(n^2).

Memory hack

Say it out loud in the interview:

1. "Is the data sorted, or may I sort it without losing what the answer needs?"
2. "After comparing a[l] and a[r], which pointer's move is provably safe, and why can't the other one help?"
3. "Loop while l < r; skip duplicates if the output must be unique."

How it works

Write down why discarding is safe; that justification is what interviewers grade.

• Pair sum (sorted): sum too small → l++ (the smallest value can't reach the target with anything). Too big → r--.
• Container With Most Water: area is limited by the shorter line. Moving the taller line can only shrink width without raising the limit, so always move the shorter one.
• Trapping Rain Water: keep leftMax and rightMax. If leftMax < rightMax, the water above l is decided by leftMax regardless of what lies between, so settle l and advance it.

Trace for Two Sum II on [2, 3, 5, 8, 11], target 13:

And with target 10:

flowchart TD
  S["l = 0, r = n - 1"] --> C{"l < r ?"}
  C -- no --> E[No answer]
  C -- yes --> V["Evaluate a[l] + a[r]"]
  V --> T{Matches goal?}
  T -- yes --> R[Record / return]
  T -- too small --> L["l++"]
  T -- too big --> Q["r--"]
  L --> C
  Q --> C

Java template

import java.util.*;

class TwoPointerToolkit {
    // Converging pointers on sorted data.
    static int[] pairSum(int[] a, int target) {
        int l = 0, r = a.length - 1;
        while (l < r) {
            int sum = a[l] + a[r];                 // problem-specific evaluation
            if (sum == target) return new int[]{l, r};
            if (sum < target) l++;                 // left side can't help with any r' <= r
            else r--;                              // right side can't help with any l' >= l
        }
        return new int[]{-1, -1};
    }

    // Fix one, converge on the rest, skip duplicates (k-sum skeleton).
    static List<List<Integer>> tripletsSummingTo(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;       // unique anchors
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                long sum = (long) nums[i] + nums[l] + nums[r];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;  // skip equal lefts
                    while (l < r && nums[r] == nums[r - 1]) r--;  // skip equal rights
                    l++; r--;
                } else if (sum < target) l++;
                else r--;
            }
        }
        return res;
    }

    // Parallel pointers, writing from the back (merge into a with spare room).
    static void mergeFromBack(int[] a, int m, int[] b, int n) {
        int i = m - 1, j = n - 1, w = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && a[i] > b[j]) a[w--] = a[i--];
            else a[w--] = b[j--];
        }
    }
}

Complexity

• Converging scan: O(n) time, O(1) space; each step moves a pointer inward, so at most n steps.
• If you must sort first: O(n log n) overall.
• 3Sum: O(n log n) sort + n anchors × O(n) scan = O(n^2); k-Sum generalises to O(n^(k-1)).
• Merge from the back: O(m + n) time, O(1) extra space.

Variations

• Target pair on sorted data: Two Sum II - Input Array Is Sorted.
• Anchor + pair (k-Sum): sort, fix one value, converge on the rest, skip duplicates. 3Sum.
• Greedy shrink by the weaker side: Container With Most Water.
• Boundary maxima from both ends: Trapping Rain Water (an O(1)-space alternative to prefix/suffix max arrays or a stack).
• Merging sorted sequences: Merge Sorted Array, filling from the end to avoid overwriting.
• Partitioning: Dutch National Flag style three-way partition with low/mid/high pointers.
• Symmetry checks: palindromes and in-place reversal.

Common mistakes

• Applying converging pointers to unsorted data, where the "safe to discard" argument does not hold.
• Sorting when the problem wants original indices and forgetting to keep them (pair values with indices first).
• In 3Sum, skipping duplicates before recording a match, or only skipping on one side, producing repeated triplets.
• Using l <= r so an element pairs with itself.
• Overflowing int when adding three large values; widen to long.

All practice problems

5 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.