Two Hands on a Number Line

Why two pointers is almost always O(n)

The promise of every two-pointer algorithm is that each pointer moves at most n times over the whole execution. That's the entire complexity argument, two pointers, each moving at most n times, gives at most 2n steps, which is O(n). You don't have to count iterations; you have to verify that neither pointer ever moves backward more than a bounded amount. Once you internalise that accounting, recognising two-pointer solutions becomes almost automatic.

The archetypal case is converging pointers on a sorted array. Place one at each end. At each step, you make a decision based on a comparison between the two values and advance exactly one pointer. The decision must be monotone: advancing must always move you "closer" to the answer in some well-defined sense. If that condition holds, the algorithm is correct and linear.

Converging pointers, three canonical shapes

Two-sum on sorted input

def two_sum(a, target):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == target: return (i, j)
        if s < target:  i += 1   # need larger - advance i
        else:           j -= 1   # need smaller - retreat j
    return None

The correctness argument: at each step, either a[i] + a[j] is the target, or it's too small (so no pair involving j can work, retreating j would only decrease the sum further), or too large (symmetric). Advancing i or retreating j eliminates exactly one element from consideration and preserves the invariant that the answer, if it exists, lies within [i, j]. The search space shrinks by one every step; after n steps, it's empty.

Valid palindrome

One pointer at each end, walk inward, skip non-alphanumeric characters, compare lowercase. O(n) in one pass with no auxiliary storage.

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        while i < j and not s[i].isalnum(): i += 1
        while i < j and not s[j].isalnum(): j -= 1
        if s[i].lower() != s[j].lower(): return False
        i += 1; j -= 1
    return True

Container with most water

Given heights, find the pair of indices whose rectangle has the largest area. Brute force is O(n²) across all pairs. Two pointers: place them at the extremes (widest possible rectangle), and at each step advance the shorter side, because shrinking the width while keeping the shorter height is guaranteed not to improve the area. O(n) with a three-line proof.

Sliding window, expand, contract, record

Sliding window is a two-pointer technique where both pointers move in the same direction. You grow the window to the right, and shrink it from the left whenever the invariant is violated. The "invariant" is problem-specific: "at most k distinct characters", "sum does not exceed S", "no repeating characters", "contains all characters of the target multiset". In every case the pattern is identical:

def template(xs):
    l = best = 0
    state = new_state()          # frequency map, sum, etc.
    for r, x in enumerate(xs):
        add(state, x)            # include xs[r] in the window
        while not valid(state):
            remove(state, xs[l]) # exclude xs[l]
            l += 1
        best = max(best, r - l + 1)
    return best

The O(n) guarantee comes from a simple observation: the left pointer only ever advances, never retreats. So across the whole run, the inner while loop does at most n total iterations. The outer for loop also runs n times. Total: at most 2n operations, linear.

Longest substring without repeating characters

def longest_unique(s):
    last = {}                    # char -> last index seen
    l = best = 0
    for r, c in enumerate(s):
        if c in last and last[c] >= l:
            l = last[c] + 1      # jump past the repeat
        last[c] = r
        best = max(best, r - l + 1)
    return best

Notice that l only moves forward, it either stays put or jumps to last[c] + 1, which is always ≥ its current value. That's the linear-time guarantee.

Fast and slow pointers

A variant where the two pointers move at different speeds through the same sequence. In linked lists, fast-and-slow finds the midpoint, detects cycles, and locates the cycle's start. On arrays with an implicit "next" function, it's the heart of the Find the Duplicate Number problem, the Floyd cycle-detection algorithm applied to i → a[i].

def find_duplicate(nums):
    # Treat index i as a node pointing to nums[i].
    # A duplicate creates a cycle; Floyd finds its entrance.
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]; fast = nums[fast]
    return slow

The derivation is pure modular arithmetic; the running time is O(n) with O(1) memory. A gorgeous algorithm with a surprising origin.

Complexity, reasoned

The converging two-pointer pattern is O(n) because each step advances one of two pointers moving toward each other; total advances ≤ n. The sliding-window pattern is O(n) because the left pointer advances at most n times across the whole execution, and the right pointer advances exactly n times. Fast-and-slow is O(n) because both pointers traverse at most the whole sequence once. Memory is O(1) for two pointers and for fast-and-slow; sliding window uses O(σ) where σ is the alphabet size, the state the window tracks.

Recognising the pattern

Reach for two pointers when the input is sorted or can be sorted cheaply, and the question asks about pairs or ranges. Reach for a sliding window when the question is about contiguous subarrays or substrings, and you can state a clear invariant. Reach for fast-and-slow when the structure is a linked list or an implicit graph with an obvious "next" function, and you are asked about cycles, midpoints, or meeting points. When none of these signals are present, the pattern probably doesn't apply, try DP or a hash map pass instead.

Where beginners go wrong

• Applying two pointers to unsorted input. The converging-pointer logic depends on monotone comparisons, which require sortedness. On unsorted input, the same pattern finds a different answer, or fails.
• Moving both pointers in converging two-sum. You move exactly one per step. Moving both discards pairs that might have been the answer.
• Sliding window without a clear invariant. "Expand and contract" is not the algorithm, the invariant is. Name the invariant before writing code; if you can't, the pattern doesn't fit.
• Off-by-one on window length. r - l + 1 is the length when l and r are both valid indices. The +1 is not negotiable.

What to read next

This is the final module. The companion deep-dive (Sliding Window in Depth) walks through three windowed problems of increasing difficulty. For an overview of where to go next, the essays cover applied patterns, interview preparation, and the texts that have shaped this curriculum.