Two Pointers

Updated Nov 19, 2026 · 4 min read
On this page

    Two pointers is what you do when a pair search would be O(n²) but the data has an order you can exploit. Two indexes move through the array, and every move rules out a whole set of candidates at once, so the total work is O(n). It needs O(1) extra space, which makes it the answer when an interviewer says "can you do it without the hash map?"

    There are two shapes. Opposite ends start at both ends of a sorted array and move inward. Same direction uses a slow writer and a fast reader moving left to right.

    When to recognise it

    • The input is sorted, or you are allowed to sort it, and you need a pair or triple with some sum or difference.
    • "Is this a palindrome?", "reverse in place", "compare from both ends".
    • "Remove / move / deduplicate in place" and return a new length: a reader and a writer.
    • Containers and walls: area or trapped water depends on the shorter of two sides, so you move the shorter side.
    • O(1) extra space is required, which rules out the hash-map version of a pair search.

    How it works: opposite ends

    On a sorted array, put lo at the start and hi at the end. If nums[lo] + nums[hi] is too small, no pair using nums[lo] can work (everything else paired with it is even smaller), so move lo right. If it is too big, the same argument removes nums[hi].

    Sorted array [1, 3, 4, 6, 8, 11], target 10. Five rows show lo and hi moving inward: 12 too big, 9 too small, 11 too big, 9 too small, then 4 + 6 = 10 found.
    Sorted array [1, 3, 4, 6, 8, 11], target 10. Five rows show lo and hi moving inward: 12 too big, 9 too small, 11 too big, 9 too small, then 4 + 6 = 10 found.
    def pair_with_sum(sorted_nums, target):
        """Opposite ends: works because the array is sorted."""
        lo, hi = 0, len(sorted_nums) - 1
        while lo < hi:
            s = sorted_nums[lo] + sorted_nums[hi]
            if s == target:
                return [lo, hi]
            if s < target:
                lo += 1          # need a bigger sum: only moving lo can give one
            else:
                hi -= 1
        return []

    Time O(n), space O(1).

    Three numbers. Fix the first number with a loop, then run the pair search on the rest. Sorting first also makes skipping duplicates easy:

    def three_sum(nums):
        """Fix one number, then run the pair search on the rest; skip duplicates."""
        nums = sorted(nums)
        out = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            lo, hi = i + 1, len(nums) - 1
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s < 0:
                    lo += 1
                elif s > 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
        return out

    Time O(n²): n fixed choices times an O(n) scan, which beats the O(n³) brute force. Sorting costs O(n log n), which does not change the total.

    Same direction: reader and writer

    read visits every element. write marks the end of the finished part. When read finds an element worth keeping, copy it to write and advance write.

    Array [1, 1, 2, 3, 3, 3, 4] with the first three cells green as the finished part [1, 2, 3]. Arrows mark write at index 3 and read at index 5.
    Array [1, 1, 2, 3, 3, 3, 4] with the first three cells green as the finished part [1, 2, 3]. Arrows mark write at index 3 and read at index 5.
    def remove_duplicates(sorted_nums):
        """Same direction (reader/writer): keep one copy of each value in place, return the new length."""
        write = 0
        for read in range(len(sorted_nums)):
            if read == 0 or sorted_nums[read] != sorted_nums[read - 1]:
                sorted_nums[write] = sorted_nums[read]
                write += 1
        return write

    The same skeleton handles "move zeroes to the end", "remove every copy of a value" and "keep at most two of each".

    Common bugs

    • Using opposite ends on unsorted input. The "too small, so move lo" argument only holds when the array is sorted.
    • lo <= hi instead of lo < hi in a pair search, which pairs an element with itself.
    • Duplicate triples in 3Sum. Skip a fixed value equal to the previous one, and after a match skip equal values on the moving side.
    • Returning indices after sorting. If the question wants original indices, sorting loses them: keep (value, index) pairs or use a hash map.
    • Moving the taller wall in container problems. The shorter wall limits the area, so only moving it can help.

    Say this in the interview

    • "The array is sorted, so if the sum is too small, the left element can't be part of any answer. I drop it and move right. Each step removes one candidate, so it's O(n) time and O(1) space."
    • "For three numbers I fix one and run the two-pointer scan on the rest: O(n²), better than O(n³)."

    Problems for this pattern

    1. Valid Palindrome: opposite ends, skipping non-letters.
    2. Valid Palindrome II: opposite ends with one allowed skip.
    3. Move Zeroes: reader and writer.
    4. 3Sum: fix one, scan the rest, skip duplicates.
    5. Container With Most Water: move the shorter wall.
    6. Sort Colors: three pointers in one pass.
    7. Trapping Rain Water: two pointers that carry the max height from each side.
    8. String Compression: a read pointer and a write pointer in the same array.

    Related

    Arrays and Strings · Sliding Window (also two indexes, but they bound a range) · Hash Maps and Prefix Sums (when the input is unsorted) · Linked List Techniques (fast and slow pointers)