Two Pointers

Opposite-end, fast/slow, and partition variants — replace nested loops on sorted/linked data with a single O(n) pass.

arrayslinked-listtwo-pointers

Three variants

  • Opposite ends — start at both ends of a sorted array, move inward based on a comparison (pair-sum, container-with-most-water, valid palindrome).
  • Fast & slow — two pointers at different speeds (cycle detection, find the middle, kth-from-end in a linked list).
  • Partition / same-direction — a write pointer trails a read pointer (remove-in-place, Dutch national flag, dedupe sorted).
Python
# Opposite ends: does a SORTED array contain two numbers summing to target?
def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target: return (lo, hi)
        if s < target:  lo += 1     # need bigger → move left pointer up
        else:           hi -= 1     # need smaller → move right pointer down
    return None

Why it's O(n): each pointer only moves one direction, so together they take ≤ n steps. The "sorted" precondition is what lets a single comparison decide which pointer to advance.

Watch it run

Converging pointers on a sorted array: every comparison moves exactly one pointer inward, so the whole scan is a single pass. Try a target with no valid pair and watch the pointers meet empty-handed.

Two pointers — pair with target sumtime O(n)space O(1)
2
0▲ i
7
1
11
2
15
3
19
4
23
5
30
6
41
7▲ j

1/6Sorted array. Does any pair sum to 34? Start with the widest pair.

target = 34

Fast & slow — cycle detection (Floyd's)

Python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # +1
        fast = fast.next.next     # +2
        if slow is fast: return True   # they meet ⇒ cycle
    return False
Two pointers vs hashing

A hash set also finds a pair-sum in O(n) time but O(n) space. Two pointers is O(1) space if the array is already sorted. If it isn't, sorting first is O(n log n) — then a hash-set pass at O(n) may win. State the trade-off out loud.

Practice — climb the ladder

Two pointers earns its keep on SORTED data or paired ends: each step discards possibilities provably, which is where the O(n) comes from.

Practice ladder: Two Pointers0/8 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Warm-up

ends moving inward, slow/fast moving forward
  1. Valid PalindromeEasy

    Ends-inward with skip rules — the cleanest convergent-pointer drill.

  2. Reverse StringEasy

    Swap-and-converge — in-place mutation with two indices.

  3. Move ZeroesEasy

    Reader/writer pointers — stable partition in one pass.

Core

the discard argument, made explicit
  1. Container With Most WaterMedium

    Move the SHORTER wall — articulate why that discard is safe; that argument IS the pattern.

  2. 3SumMedium

    Sort + fix one + two-pointer the rest, with dedup discipline — the interview staple.

  3. Remove Duplicates from Sorted Array IIMedium

    Writer pointer with a look-back condition — in-place with a twist.

Stretch

maximum discard sophistication
  1. 4SumMedium

    The 3Sum skeleton generalized — nested fixing without drowning in dedup.

  2. Trapping Rain WaterHard

    Two pointers with running maxes from both ends — the famous finale.