Two pointers

Problem

Brute force on "find a pair" or "best pair of positions" checks all O(n²) pairs. When the input has order (sorted values, or a quantity that depends on the distance between positions), you can often prove that a whole row of pairs cannot contain the answer, and skip it. Two pointers are the bookkeeping for that proof.

Intuition

Imagine looking for two numbers that add to 14 in a sorted row, with a finger on each end. If the two numbers are too big, the right-hand finger's number is too big for every partner, because the left finger holds the smallest partner it could have. So that number can be ruled out entirely and the finger steps inward. The symmetric argument discards the left number when the sum is too small. Each step eliminates a whole row or column of the pair table, so n steps cover n² pairs.

Amber cells are the pointers; blue cells are ruled out and never looked at again.

Mechanics

The invariant

For converging pointers left < right, the invariant is: if a solution exists, it lies within [left, right]. Each move must preserve that. In the sorted pair sum, when nums[left] + nums[right] > target, the value at right plus anything at or after left is at least as large, so right belongs to no solution and can be dropped. The mirrored argument covers "too small". The loop ends when the pointers meet, with the window empty, which proves there was no solution.

The same proof for containers

Water held between two walls is min(h[left], h[right]) × (right − left). Say the left wall is the shorter. Any container using this wall and a position inside the window has smaller width and height still capped by this wall, so it cannot beat the current one. The left wall is finished: step it inward. Moving the taller wall instead could only lose width without lifting the cap, so that choice is never needed. This is an exchange argument, and it is what you say aloud in an interview.

Reducing to pairs

For three sum, sort and fix the smallest element at index i. The rest is the converging pair search for the target −nums[i] on the suffix after i. Duplicates are handled by skipping a fixed value equal to the previous fixed value, and by stepping the left pointer past repeats after a hit. Sorting costs O(n log n) and the n pair searches cost O(n²), so the total is O(n²), against O(n³) for brute force.

Green walls are the best pair. Every other pair was discarded by the move rule without being evaluated.

Worked example

Pair sum 14 in [1, 3, 4, 6, 8, 11, 15]: 3 comparisons instead of 21 pairs.

Container with heights [1, 8, 6, 2, 5, 4, 8, 3, 7]:

The answer is 49. In the first step the left wall (height 1) is the shorter, so it moves, exactly as the proof says: it can never be part of anything larger.

Three sum on [-1, 0, 1, 2, -1, -4, -1] sorts to [-4, -1, -1, -1, 0, 1, 2] and finds the triples [-1, -1, 2], [-1, 0, 1], after skipping the repeated −1 values as fixed elements.

Implementation

def pair_sum_sorted(nums, target):                  # indices, or None
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None


def max_area(heights):
    left, right, best = 0, len(heights) - 1, 0
    while left < right:
        best = max(best, min(heights[left], heights[right]) * (right - left))
        if heights[left] <= heights[right]:
            left += 1
        else:
            right -= 1
    return best


def three_sum(nums):
    nums.sort()
    out = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                out.append([nums[i], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
    return out


def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        if not text[left].isalnum():
            left += 1
        elif not text[right].isalnum():
            right -= 1
        elif text[left].lower() != text[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Variations and edge cases

• Same-direction pointers. The read and write indices from the previous page are two pointers moving the same way. Merge two sorted lists uses one pointer per list.
• Almost-palindrome. On the first mismatch, try skipping the left character or the right one and check the rest with the plain palindrome test; at most one skip is allowed.
• Closest sum. Same converging loop, but track the sum nearest to the target instead of stopping at equality.
• Four sum and k-sum. Add outer loops (each with duplicate skipping) around the pair search; the cost is O(n^(k−1)).
• Greedy pairing. Boats and similar problems: sort, then pair the heaviest remaining with the lightest when they fit, otherwise take the heaviest alone.
• Three-way partition. Keep low, mid, high; swap 0s behind low and 2s ahead of high. Do not advance mid after swapping with high, since the value that arrived is unexamined.
• Edge cases: fewer than two (or three) elements, all equal values with duplicate skipping, using < versus <= in the loop condition (a pointer must not pair with itself), unsorted input (sort first, and remember the original indices if the answer asks for them), and overflow in other languages.

Complexity and tradeoffs

• Time: O(n) for a single converging pass; O(n log n) if sorting is needed first; O(n²) for three sum.
• Space: O(1) beyond the sort (and the output).
• Baselines. Brute force is O(n²) for pairs. A hash map solves unsorted pair sum in O(n) time and O(n) space and also preserves indices; choose the hash map when the array is unsorted and the answer needs original positions.
• When it fails. If neither pointer move can be justified by a monotonic argument, the pattern does not apply. Negative numbers break window-style pointers that move in the same direction (see prefix sums), but converging pointers on a sorted array are fine with negatives.

Problems

Home problems range from reversing a string through sorted pair searches to the container and rain-water problems, whose correctness rests on the discard argument above.

Easy

• 26. Remove Duplicates from Sorted Array NeetCode 250
  A slow writer pointer keeps the unique prefix while a fast reader skips anything equal to the last value written.
• 88. Merge Sorted Array NeetCode 250
  Fill the first array from the back, taking the larger tail each time, so nothing is overwritten before it is read.
• 125. Valid Palindrome Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Move two pointers inward, skipping non-alphanumeric characters, and compare lowercase letters until they meet.
• 283. Move Zeroes Grind 169
  Move each non-zero element forward to a write pointer, then the slots after it are all zeros.
• 344. Reverse String NeetCode 250
  Swap the two ends and move both pointers inward until they meet.
• 680. Valid Palindrome II NeetCode 250
  Move inward until the first mismatch, then check whether skipping either of the two characters leaves a palindrome.
• 844. Backspace String Compare Grind 169
  Scan both strings from the end, skipping characters erased by backspaces, and compare the next surviving characters.
• 977. Squares of a Sorted Array Grind 169
  The largest square is at one of the two ends, so fill the result from the back with the larger end's square.
• 1768. Merge Strings Alternately NeetCode 250
  Take one character from each string in turn, then append whatever is left of the longer string.

Medium

• 11. Container With Most Water Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Start with the widest container and always move the shorter wall inward, since keeping it can never produce a larger area.
• 15. 3Sum Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Sort, fix the smallest element, and run a converging pair search on the rest, skipping equal neighbours to avoid duplicate triples.
• 16. 3Sum Closest Grind 169
  After sorting, fix one element and converge a pair on the rest, keeping whichever sum has landed closest to the target.
• 18. 4Sum NeetCode 250
  Fix two outer elements in nested loops over the sorted array, then let a converging pair finish the sum, skipping duplicates at every level.
• 75. Sort Colors Grind 169 NeetCode 250
  Partition into three zones with low, mid and high pointers, swapping 0s down and 2s up while mid scans.
• 167. Two Sum II - Input Array Is Sorted NeetCode 150 NeetCode 250
  With the array sorted, a sum that is too small moves the left pointer right and a sum that is too large moves the right pointer left.
• 881. Boats to Save People NeetCode 250
  Sort, then pair the heaviest remaining person with the lightest whenever they fit together, otherwise send the heaviest alone.

Hard

• 42. Trapping Rain Water Grind 169 NeetCode 150 NeetCode 250
  Water above a bar is set by the smaller of the tallest walls on its left and right, so move inward from whichever side's tallest wall is lower.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 27. Remove Element Easy
• 5. Longest Palindromic Substring Medium
• 31. Next Permutation Medium
• 189. Rotate Array Medium
• 658. Find K Closest Elements Medium

Connections

Sliding windows are two pointers that move in the same direction, and fast and slow pointers on linked lists use the same machinery with different movement rules. Binary search is the extreme case of discarding half the range per step. Greedy exchange arguments, like the one for containers, appear again on the greedy page.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: the merge step of merge sort (section 2.3) and the discussion of loop invariants.
• Sedgewick and Wayne, Algorithms: section 2.2 on merging and section 2.3 on partitioning.
• Steven Skiena, The Algorithm Design Manual: the section on sorting and searching applications, including pair and closest-pair searches.
• Edsger Dijkstra, "Dutch national flag" in A Discipline of Programming (1976), the origin of the three-way partition.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.