Two Pointers and the Sliding Window

Two-pointer techniques look like nothing — two indices walking through an array. They eliminate a layer of nested looping that would otherwise make the algorithm O(n²).

Pattern 1: opposite ends

Sorted array, find a pair 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
        else:
            hi -= 1
    return None

Each iteration advances one pointer and never moves it back. O(n).

Pattern 2: same direction (sliding window)

Longest substring with at most k distinct characters.

from collections import Counter

def longest_at_most_k(s, k):
    counts = Counter()
    best = lo = 0
    for hi, ch in enumerate(s):
        counts[ch] += 1
        while len(counts) > k:
            counts[s[lo]] -= 1
            if counts[s[lo]] == 0:
                del counts[s[lo]]
            lo += 1
        best = max(best, hi - lo + 1)
    return best

The window s[lo:hi+1] always satisfies the constraint. When extending the window breaks it, we shrink from the left until it's valid again. Each character is added and removed at most once, so this is O(n).

When the technique applies

You're looking for a subarray or subsequence satisfying some monotone constraint:

• "longest with at most k distinct" — adding a character can only increase the constraint, removing only decreases it
• "smallest window containing all of T" — same shape
• "max sum of length-k window" — fixed-size window slides one step at a time

If the constraint isn't monotone (e.g., "exactly k distinct"), you often solve it as the difference of two "at most" problems: exactly k = at_most_k - at_most_(k-1).