Two-Pointer Technique — Recognition, Move Rules, Three Walkthroughs

Two-pointer is what happens when you stop asking "which pair should I check next?" and start asking "which pair can I safely rule out?" That reframing is the whole technique — the code that follows writes itself.

Recognition — when to reach for it

Two-pointer is the right tool when all four of these hold:

The input is a linear sequence — an array or a string — and the answer is either a pair of elements or a boolean about symmetry.
You're asked to find, verify, or count something that depends on values at two positions at once.
The input is sorted, can be sorted without losing information, or is symmetric (as in a palindrome check).
The brute force is O(n²) — try every (i, j) pair — and most of that work is provably wasted.

That "sorted or symmetric" bar is load-bearing. Without it, moving a pointer doesn't safely eliminate anything, and the technique collapses back to brute force. LeetCode 1 Two Sum on an unsorted input with "return the original indices" is the canonical example of a problem that looks two-pointer but is really a hash-map problem — sorting scrambles the indices you're required to return.

Mental model — why it collapses to O(n)

Two indices bracket the current candidate: left on one end, right on the other. Each move eliminates a swath of pairs without checking them. That's the trick — you're not iterating over n² pairs; you're doing n moves, each of which prunes some subset of the search space based on an invariant the problem gives you.

Each pointer moves at most n times, so total work is at most 2n. That's O(n), plus O(n log n) if the input needed sorting first.

Three flavours worth naming

Converging (opposite ends). left starts at 0, right starts at n − 1, they close toward each other. Needs sorted-or-symmetric input. This is the classic, and the focus of this post.
Same-direction (fast/slow). Both pointers start at the same end; one advances under a different condition than the other. Great for in-place partitioning, cycle detection, and de-duplication. Enough of its own to justify a separate post — see the fast/slow pointers write-up in the roadmap.
Parallel arrays. One pointer per array, walking two inputs simultaneously. Merging sorted lists, computing set intersections, walking transcripts against a template. Mechanically two-pointer, but the recognition signal ("I have two sequences and need to align them") is different enough that most learners think of it as a distinct pattern.

The rest of this post is about converging two-pointer.

The move rule — the whole art

Every converging two-pointer problem is defined by its move rule: given the current (left, right) state, which pointer advances, and why? Get this rule right and the loop writes itself. Get it wrong and the technique silently degrades to O(n²) or, worse, misses the answer.

Three examples up front, to make the shape concrete before the walkthroughs:

Palindrome check. Both move inward every step, unless the characters don't match — in which case return false.
Two-sum on a sorted array. If the pair's sum is too small, move left forward (the only way to grow the sum). If too big, move right backward. If equal, done.
Container with most water. Move the pointer at the shorter wall. Moving the taller wall can never help (width shrinks, height stays clamped by the shorter wall); moving the shorter wall might unlock a taller minimum height and offset the width loss.

If you can state the move rule for a new problem in one sentence, you've solved the interesting half of it.

The template

def two_pointer_converging(arr):
    left, right = 0, len(arr) - 1
    best = init_best()

    while left < right:
        # Read arr[left], arr[right]. Decide the answer contribution.
        best = update(best, arr[left], arr[right])

        # Apply the move rule.
        if should_move_left(arr[left], arr[right]):
            left += 1
        elif should_move_right(arr[left], arr[right]):
            right -= 1
        else:
            # Both pointers move (palindrome-style equal step).
            left += 1
            right -= 1

    return best

Everything below is a filling for update and the should_move_* predicates.

Walkthrough 1 — LeetCode 125, Valid Palindrome

Given a string, return true if it reads the same forward and backward after stripping non-alphanumeric characters and lowercasing. Empty strings count as palindromes.

Recognition. Symmetric structure (palindrome ✓). Linear string ✓. Brute force is "reverse the filtered string and compare" — O(n) but wasteful of memory. Two-pointer trims the extra allocation and generalises to streaming variants.

Move rule. Both pointers move inward each step. If either lands on a non-alphanumeric character, skip it (advance only that pointer). If the two characters don't match after lowercasing, return false.

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Trace s = "A man, a plan, a canal: Panama". left and right step past commas, spaces, and the colon, then compare the letter pairs A/a, m/m, a/a, n/n, a/a, p/p, l/l, a/a, n/n, a/a — all match — before converging on the single middle c. Result: true.

The two inner while loops are the load-bearing detail. If either forgets to check left < right, a fully non-alphanumeric input walks past the boundary and dies on an index error.

Walkthrough 2 — LeetCode 11, Container With Most Water

Given an array of heights, pick two indices (i, j) maximising the rectangle bounded by the two lines: (j − i) × min(height[i], height[j]).

Recognition. Pair problem ✓. Linear input ✓. Not sorted, but the problem has a monotone shrinkage invariant — as the window narrows, height has to grow to compensate. Brute force is O(n²).

Move rule. The move that unlocks O(n) is: move the pointer at the shorter wall. Why? Because the current water is bounded by min(height[left], height[right]). If we move the taller wall, the new width is smaller AND the height can't exceed the shorter wall's height — no improvement possible. If we move the shorter wall, the new minimum height might be taller, and might compensate for the smaller width.

That's not a heuristic; it's a proof of correctness. Every pair the shorter-wall-moves rule skips is provably worse than the current best.

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = (right - left) * min(height[left], height[right])
        best = max(best, water)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Trace heights = [1, 8, 6, 2, 5, 4, 8, 3, 7].

left	right	water	move
0	8	min(1, 7) × 8 = 8	move left (1 < 7)
1	8	min(8, 7) × 7 = 49	move right (7 ≤ 8)
1	7	min(8, 3) × 6 = 18	move right
1	6	min(8, 8) × 5 = 40	move right
1	5	min(8, 4) × 4 = 16	move right
1	4	min(8, 5) × 3 = 15	move right
1	3	min(8, 2) × 2 = 4	move right
1	2	min(8, 6) × 1 = 6	move right

Best: 49. Nine array reads instead of 36 pairs — the O(n) collapse in action.

Walkthrough 3 — LeetCode 15, 3Sum

Given an array, return every unique triple (a, b, c) with a + b + c = 0.

3Sum is the interview-classic two-pointer problem. It also shows the technique's biggest superpower: nest it inside an outer loop and the O(n²) triple search collapses to O(n²) with a small constant, which is asymptotically the best possible for this problem.

Recognition. Triple problem ✓. Not sorted — but nothing forbids us from sorting; we're returning values, not indices. Brute force is O(n³). Sorting + two-pointer on each outer index is O(n²).

Move rule. For each fixed nums[i], two-pointer the subarray i+1..n-1 looking for a pair summing to -nums[i]. Sum too small → move left forward. Too big → move right back. Equal → record, then skip duplicates on both sides.

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    n = len(nums)
    result = []

    for i in range(n - 2):
        # Once nums[i] > 0, no triple summing to zero can start here.
        if nums[i] > 0:
            break
        # Skip duplicate anchors so we don't emit the same triple twice.
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        target = -nums[i]
        left, right = i + 1, n - 1

        while left < right:
            s = nums[left] + nums[right]
            if s < target:
                left += 1
            elif s > target:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # Dedupe both sides before advancing.
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result

Trace nums = [-1, 0, 1, 2, -1, -4]. After sorting: [-4, -1, -1, 0, 1, 2].

i = 0 (nums[i] = -4): target = 4. Two-pointer sweeps [-1, -1, 0, 1, 2]. No pair sums to 4; nothing recorded.
i = 1 (nums[i] = -1): target = 1. Finds (-1, 2) (sum 1) → record [-1, -1, 2]. Advances past dupes. Finds (0, 1) (sum 1) → record [-1, 0, 1].
i = 2 (nums[i] = -1): duplicate of i = 1, skipped.
i = 3 (nums[i] = 0): target = 0. Two-pointer on [1, 2]; sum 3 > 0, right moves; loop ends. Nothing recorded.

Result: [[-1, -1, 2], [-1, 0, 1]].

The three dedupe rules are the part interviewers grade: anchor dedupe (skip nums[i] == nums[i-1]), left dedupe after hit (skip nums[left] == nums[left+1]), right dedupe after hit (skip nums[right] == nums[right-1]). Miss any one and the output has duplicate triples. Interviewers will notice.

When two-pointer is not the tool

Same recognition checklist, failure modes made explicit:

Return the original indices of an unsorted input. LC 1 Two Sum. Sorting loses the mapping. Hash map.
You need every subarray with a property, not just an optimal pair. Sliding window territory (see the sliding-window post) — extend + contract on the same end, not converge from opposite ends.
The invariant isn't monotone. If moving left forward doesn't provably discard weaker candidates, the technique degenerates to brute force. Reach for DP, prefix sums, or hashing instead.
You need more than two positions with no useful nesting. 4Sum and generic k-Sum extend the two-pointer idea by adding an outer loop per extra element, but each level costs a factor of n. Past k = 3, hashing often wins.

If you write the loop and find yourself unable to justify why moving the pointer is safe — not just "seems to work on the sample" — the pattern is wrong for this problem. Rethink the invariant.

How the Algotrek tutor would prompt you here

When a learner opens a converging two-pointer problem on Algotrek, the tutor doesn't reveal the code. It asks three questions, and advances only when each is answered in one sentence:

"What's the brute force, and where's the redundant work?" — Forces the learner to see the O(n²) baseline and identify pairs that can never beat the current best.
"State the invariant that lets you move a pointer safely." — This is the technique. "Moving the shorter wall never worsens the answer" for LC 11. "If sum < target, moving left forward is the only way to grow it" for LC 15's inner loop. If you can't articulate it, you're not ready to code.
"Given the current (left, right), which pointer moves? Why?" — This is the move rule. Naming it out loud is what turns memorised code into a tool you can carry to a new problem.

Answer all three and the loop is a five-minute typing exercise. Miss one and you'll re-derive the wrong solution three times before noticing. Try the Valid Palindrome lesson on Algotrek to see the prompt-then-reveal flow on the friendliest converging two-pointer problem, then step up to the 3Sum lesson once the move-rule habit is in your fingers.

Where to go next

LC 42, Trapping Rain Water. Converging two-pointer with a running max from each side. The move rule is genuinely subtle — worth working out on paper before typing. A common alternative is a monotonic-stack solution; comparing the two is a good study in "same problem, two invariants".
LC 26, Remove Duplicates from Sorted Array. Same-direction / fast-slow flavour: slow marks the write cursor, fast scans. A clean introduction to the second flavour above.
LC 88, Merge Sorted Array. Parallel-arrays flavour, plus the "iterate backward so writes don't clobber future reads" twist.
LC 977, Squares of a Sorted Array. Converging two-pointer that builds the output in reverse — a nice reminder that "which direction the output grows in" is a design choice.
Cross-reference the sliding-window post. Sliding-window and two-pointer share the "two indices bracket a region and move under an invariant" bone structure. The difference is direction: sliding-window's pointers move together (extend right, contract left); two-pointer's converge. Learn both deeply and 40% of LeetCode's medium tier feels like the same problem in different hats.

If you can walk into LC 11, LC 15, and one of LC 42 or LC 26 cold and write them in under 15 minutes each, converging two-pointer is yours. That's a real skill, and it's the one interviewers reach for when they want to see whether you can reason about invariants — not just recall a solution.

For the O(n log n) sort claim that unlocks 3Sum and the O(n) two-pointer scan that follows, see the Big-O cheat sheet — the sorting-algorithms and language-gotchas sections both pay off directly on this pattern.