Two Pointers

The idea

Replace nested loops with two indices that each move at most n times → O(n) time, O(1) space. Three flavors cover almost everything: pointers that converge from the ends, pointers that chase in the same direction, and pointers walking two sequences at once.

Converging pointers (sorted input)

A left/right pair on a sorted array decides which side to move from the current state:

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target: return [lo, hi]
        if s < target:  lo += 1        # need a bigger sum
        else:           hi -= 1        # need a smaller sum
    return []

Same shape:

• Valid palindrome — compare from both ends inward.
• Container with most water — move the shorter wall inward (it’s the limiting one).
• Trapping rain water — two pointers tracking left/right max walls, O(1) space.
• 3Sum / 4Sum — sort, fix one (or two) elements, two-pointer the rest; skip duplicates.

Same-direction (fast/slow, write pointer)

A write pointer trails a read pointer to compact/partition in place:

def remove_duplicates(nums):           # sorted; returns new length
    w = 0                              # write index
    for r in range(len(nums)):
        if r == 0 or nums[r] != nums[r-1]:
            nums[w] = nums[r]; w += 1
        # else skip the duplicate
    return w

This pattern does move zeroes, remove element, and partition (Dutch National Flag: three pointers split <, =, > a pivot in one pass). On linked lists, fast/slow finds the middle and detects cycles (Floyd’s — see the linked-lists primer).

Two sequences at once

Two pointers march through two arrays/lists:

• Merge two sorted arrays — advance whichever front is smaller.
• Is subsequence — advance the pattern pointer only on a match; O(n).
• Intersection of sorted arrays — advance the smaller; collect equal.
• Merge step of merge sort — the same move (see the sorting / divide-and-conquer primers).

Sliding window is a specialization

A window [left, right] where both pointers move forward is a two-pointer pattern — important enough to have its own primer. Reach for it on “longest/shortest contiguous subarray with a constraint.”

When to reach for it

• The array is sorted (or sortable) and you need a pair/triplet summing/comparing to a target.
• You’re removing/partitioning in place (O(1) space).
• A brute force compares every pair — converging or chasing pointers usually collapse it to one pass.
• Merging or comparing two ordered sequences.

Pitfalls

• Unsorted input — converging two-pointer needs sorted data (sorting costs O(n log n), which may or may not beat a hash map’s O(n)/O(n)).
• Duplicate handling in 3Sum-style problems — skip equal values to avoid duplicate triplets.
• Off-by-one in the while lo < hi boundary and the write index.

State the trade: “two pointers gives O(1) space if I can sort; a hash map gives O(n) time without sorting” — choosing between them is the signal.