Mastering the Two Pointers Technique (with Patterns & Code)

Two pointers collapses a nested-loop O(n²) scan into a single O(n) pass by walking two indices instead of restarting an inner loop. You reach for it when the brute force re-scans the array and the data has structure you can exploit — usually sorted order, or a notion of positional progress that lets one index trail another. There are three variants worth having in your fingers, and the part interviewers actually probe is not the code but why the elimination it performs is legal.

Recognition cues

The last row matters as much as the others: two indices bounding a contiguous range you grow and shrink is a different pattern with a different invariant, and naming it correctly out loud is worth more than either implementation.

Why converging pointers are O(n), not O(log n)

This is the most common misunderstanding of the pattern, and it comes from a false analogy: "each comparison throws away part of the search space, so it must be logarithmic." It is not, and the reason is worth being precise about, because interviewers ask.

Take a sorted array and lo < hi. If nums[lo] + nums[hi] < target, then nums[lo] cannot reach the target with any index still in play — nums[hi] is its largest remaining partner, since every other candidate sits between lo and hi and by sortedness holds a value no larger. So one comparison retires nums[lo] together with all hi − lo pairs it had left. The symmetric argument retires nums[hi] when the sum is too large.

That gives you the invariant: every pair that could still satisfy the condition lies strictly inside the window [lo, hi]. Each iteration shrinks that window by exactly one, so the loop runs at most n − 1 times and no candidate pair is ever discarded wrongly. Linear time, constant space.

Now the distinction from binary search. Binary search bisects a linear space of n candidate positions and halves it per comparison: log n steps. Two pointers walks a quadratic space of about n²/2 candidate pairs and removes one entire row or column per comparison — roughly n pairs at a time, n times over. Halving a line gives you a logarithm; peeling rows off a square gives you a line. Both are "eliminate on each comparison"; they are eliminating from spaces of different dimension, which is why the answers differ.

Worth saying out loud: the real alternative here is not brute force, it is binary-searching each element's complement — O(n log n). Two pointers beats that because it reuses the previous comparison instead of restarting the search each time.

Variant 1: converging (opposite ends)

Start at both ends, move inward based on a condition.

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:                       # `<`, not `<=`: i and j must differ
        total = nums[lo] + nums[hi]
        if total == target:
            return [lo, hi]
        if total < target:
            lo += 1                      # nums[lo] is retired: it can go no higher
        else:
            hi -= 1                      # nums[hi] is retired: it can go no lower
    return []

static int[] twoSumSorted(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int total = nums[lo] + nums[hi];
        if (total == target) {
            return new int[] { lo, hi };
        }
        if (total < target) {
            lo++;
        } else {
            hi--;
        }
    }
    return new int[0];
}

The same skeleton drives Valid Palindrome and Container With Most Water, the one converging problem whose argument is genuinely non-obvious. There you always move the shorter wall, and the justification is the same elimination shape: any pair using that wall and an index inside the current window has less width and no more height, so it cannot beat the area you just measured. The shorter wall is retired, not merely skipped.

Variant 2: same-direction read/write (in-place partition)

This is the variant most write-ups skip, and it is asked constantly — every "do it in place with O(1) extra space" question is this shape. A write index trails a read index: read advances every iteration, write only when something is kept. Because write ≤ read always holds, you never overwrite a cell you have not already consumed.

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:   # compare to the last KEPT value
            nums[write] = nums[read]
            write += 1
    return write                            # nums[:write] is the deduped prefix

static int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int write = 1;
    for (int read = 1; read < nums.length; read++) {
        if (nums[read] != nums[write - 1]) {
            nums[write++] = nums[read];
        }
    }
    return write;
}

The comparison is against nums[write - 1], the last value you kept — not nums[read - 1], the value you last looked at. They coincide until the first duplicate is dropped and diverge forever after. Comparing to read - 1 happens to work for plain dedup and breaks immediately on the "at most twice" variant, where the correct test is nums[write - 2].

Move Zeroes is the same loop with nums[read] != 0 as the keep test, then zero-filling the tail (or swapping instead of copying, if asked to minimise writes).

The three-way generalisation is Dutch national flag — one pass, three regions, no sort:

static void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {                 // `<=`: nums[high] is still unexamined
        if (nums[mid] == 0) {
            swap(nums, low++, mid++);     // swapped-in value is already processed
        } else if (nums[mid] == 2) {
            swap(nums, mid, high--);      // do NOT advance mid: new value is unseen
        } else {
            mid++;
        }
    }
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

The invariant: everything before low is 0, [low, mid) is 1, everything after high is 2, and [mid, high] is unknown. Advancing mid after the high swap is the classic bug — it steps over a value nothing has looked at, and the array comes out almost sorted, which is the worst kind of wrong because small test cases still pass.

Variant 3: fast & slow

Two pointers over the same sequence at different speeds. The speed gap is the measurement: if a cycle exists the fast pointer must eventually be lapped into the slow one, and if it does not exist the fast pointer runs off the end.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:            # both guards required before .next.next
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False


def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow                          # even length -> second of the two middles

static boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

static ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Both functions are the same loop; only the return differs. Two things to say before being asked. The null guard is fast != null && fast.next != null — you are about to dereference two links, so you check two. And on an even-length list this returns the second middle node; starting fast at head.next returns the first. Neither is more correct, but the problem statement has an opinion, so state which one you implemented.

The follow-up — where does the cycle start — has a short proof rather than a memorised incantation; it is covered in the complete DSA patterns guide alongside the other sixteen shapes.

The triplet case, honestly

3Sum is where people quote the wrong complexity. Fixing one element and running the converging scan inside it is O(n²), plus an O(n log n) sort the quadratic term absorbs. It is not linear, and saying it is reads as not having thought about the loop you just wrote.

What actually fails interviews here is deduplication. Sorting groups equal values together, which makes duplicate triplets both easy to produce and easy to skip — if you skip in the right direction.

def three_sum(nums):
    nums.sort()
    n, out = len(nums), []
    for i in range(n - 2):
        if nums[i] > 0:
            break                                  # smallest is positive: no zero sum
        if i > 0 and nums[i] == nums[i - 1]:
            continue                               # compare BACKWARD, never forward
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                out.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
    return out

Three details carry the correctness:

• The outer skip compares to i - 1, not i + 1. Writing if nums[i] == nums[i + 1]: continue is the near-miss that costs people the problem. On [-1, -1, 0, 2] it skips the first -1 and never finds [-1, -1, 2] — a valid triplet that needs the duplicate. Skipping backward drops repeat starting points; skipping forward drops repeat values, which is not the same thing.
• The inner skips run after recording, not before. Record the first hit at each value, then step over every equal neighbour.
• Both inner skips re-test lo < hi. Without it, a run of identical values walks the pointers past each other and you index outside the window.

The skeleton generalises: 4Sum is two nested fixed elements around the same pair scan — O(n³), with dedup at every level.

Named problems and what each one is testing

• Two Sum II — Input Array Is Sorted. Tests whether you notice the word "sorted". A hash map is a correct answer here that throws away the O(1) space the problem is offering you.
• Valid Palindrome. Tests bounds discipline inside a nested loop: the skip-non-alphanumeric while loops must each re-check left < right, or a string of pure punctuation walks off the end.
• Container With Most Water. Tests whether you can justify moving the shorter line. Everyone can state the rule; the interview is the argument for why the discarded pairs are dominated.
• 3Sum. Tests dedup discipline and honest complexity, in that order.
• Remove Duplicates from Sorted Array II. Tests whether you understood read/write or memorised it — the "at most twice" version needs nums[write - 2], which only makes sense if you know what write means.
• Sort Colors. Tests the three-way invariant and the "do not advance mid" subtlety — the cleanest test of stating a loop invariant under pressure.
• Linked List Cycle / Middle of the Linked List. Tests null-safety and whether you name the even-length convention unprompted.

Failure modes

• Using converging pointers on unsorted input. The elimination argument dies without ordering, and the code still runs and returns a plausible wrong answer. If order is not guaranteed, either sort — paying O(n log n) and losing the original indices — or use a hash map.
• while lo < hi versus lo <= hi. For pair problems, <= reports an element paired with itself, a false positive exactly when the target is twice that value. For Dutch flag, <= is required, because high points at something not yet examined. It follows from whether a pointer names a distinct item or an unprocessed boundary.
• Forgetting duplicate skipping. In 3Sum this shows up as a correct-looking answer with repeated triplets. Deduplicating the output afterwards with a set works, but throws away the sortedness you paid for and reads as patching over a gap.
• Mutating while reading in the partition variant. The safety property is write ≤ read at every step. Break it — by advancing write on a branch that kept nothing, or by swapping in a value from an unexamined region and stepping over it — and you overwrite data you still needed.
• Not moving a pointer on some branch. Every branch must advance something. One that does not is an infinite loop, and it will be the branch your examples do not hit.

Complexity, stated properly

Quote the row you actually implemented. "Two pointers is linear" is true of one row and false of two others, and the gap between "O(n²), because the pair scan runs inside a loop over the fixed element" and "two pointers, so linear" is visible immediately.

Pick two problems from each variant and write them cold, without these templates in front of you — recognition is trained by being wrong and correcting, not by rereading. Build the schedule with the free study-plan generator, or work through them in the DSA course, where you name the invariant out loud before you are allowed to type.

Two pointers is one of seventeen shapes worth recognising on sight; the complete DSA patterns guide has the recognition table and the signal that picks this one over the rest.

More interview patterns: Sliding Window · Binary Search · Dynamic Programming · Graph Algorithms

New pattern breakdowns go out as they publish — get them by email.

Amit Singh teaches the DSA cohort at AlgoEngineer, works as a Senior SDE at Amazon, and is a Claude Certified Architect.