Two Pointers

No. 13 · SVG · Calipers closing inopposite ends · pairs · triplets · palindromes

Drag across the pointers. Click it, then use ← → to step and Space to play.

Two indexes, usually starting at opposite ends, move toward each other based on a comparison. It works because sorted order tells you which pointer to move: if the pair's sum is too small, the left value is too small for every partner still in range, so it can be ruled out and L moves right; if it is too big, R moves left. Every step rules out one element for good, so the pointers meet after at most n steps: O(n) time with O(1) space, instead of O(n²) for every pair.

FIG. 13 · The array sits in a type case like on page 1. L is the tag above the row and R the tag below it (in the examples, i is the black tag above). The red frame spans what is still possible; it turns dashed red just before a pointer moves, and the tiles left outside fade because they have been ruled out. Callout: A the input.

Step 1 / 1
READY
Slides
Extra space
Window
Result
Codetwo_sum_sorted
def two_sum_sorted(nums, target):  # Two Sum II
    L, R = 0, len(nums) - 1
    while L < R:
        s = nums[L] + nums[R]
        if s < target:
            L += 1                 # need bigger
        elif s > target:
            R -= 1                 # need smaller
        else:
            return [L, R]
    return []

Examples

Two pointers · LeetCode 11

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. Water between two walls is width × the shorter wall. Start with the widest pair and always move the shorter wall inward, because moving the taller one can only lose width. Answer: 49. Trigger: "container with most water".

O(n) timeO(1) spaceone area per step instead of all n(n − 1)/2 pairs
Sort + two pointers · LeetCode 15

nums = [-1, 0, 1, 2, -1, -4]. Sort, fix the first number with i, then find pairs summing to −nums[i] with two pointers, skipping duplicates. Answer: [[-1, -1, 2], [-1, 0, 1]]. Trigger: "find a triplet".

O(n²) timeO(1) extra spacen starting points × one O(n) pointer pass; sorting is O(n log n)

Time and space

ProblemTimeSpaceWhy
Pair in a sorted array, palindrome, containerO(n)O(1)Each step moves one pointer inward and they never move back, so at most n steps.
Triplet (3Sum)O(n²)O(1) extraOne O(n) two-pointer pass for each of n first numbers, after an O(n log n) sort.
Brute force: every pairO(n²)O(1)n(n − 1)/2 pairs. The pointers skip all but n of them, safely.
Hash map Two Sum (page 9)O(n)O(n)Works on unsorted input but needs memory. Sorted input? Two pointers get O(1) space.

Why is it safe to skip?

With L and R at the ends of a sorted range, if nums[L] + nums[R] is too small, then nums[L] plus any value in the range is too small, because nums[R] is the largest of them. So nums[L] can't be in any answer, and dropping it loses nothing. The same argument, mirrored, drops nums[R] when the sum is too big. Every step removes one candidate with proof.

Two pointers vs sliding window

Both use L and R. A sliding window (page 12) has both pointers moving the same direction, keeping a contiguous stretch. Two pointers usually start at opposite ends and squeeze inward, using sorted order or symmetry to decide which side to give up.

Trigger words: when the problem wants two pointers

Opposite ends

  • sorted array, find a pair
  • find a triplet
  • container with most water

Compare the ends; move the pointer the comparison rules out.

Mirror pairs

  • palindrome
  • reverse in place

Pair position i with its mirror n − 1 − i and step both inward.

Template

def two_sum_sorted(nums, target):  # Two Sum II
    L, R = 0, len(nums) - 1
    while L < R:
        s = nums[L] + nums[R]
        if s < target:
            L += 1                 # need bigger
        elif s > target:
            R -= 1                 # need smaller
        else:
            return [L, R]
    return []

def is_palindrome(s):
    L, R = 0, len(s) - 1
    while L < R:
        if s[L] != s[R]:
            return False
        L, R = L + 1, R - 1
    return True