38Two pointers & the sliding window

In Chapter 37 we bought O(1) lookups by trading extra memory for speed with a hash table. Here we get that same collapse of a nested loop, but pay nothing extra at all. The plan is two array patterns, one after the other. First, two pointers that march in from both ends and let the data rule itself out. Then a sliding window that updates its running answer as it moves instead of rebuilding it from scratch. All the way through, we keep asking the one question that turns O(n²) into O(n): how much of this work did the previous step already do for me? By the end you'll look at a nested double loop and see whether it's secretly a single sweep in disguise — and know exactly how to set it free.

01Two fingers, marching inward

Let's start with the array you already know from Volume 1: a row of contiguous slots, where a[i] is a single multiply-and-jump — O(1) random access. The usual way to walk it is one index sliding left to right, and for most jobs that's exactly right. But watch for a particular shape of problem: one with a hidden symmetry, where the answer depends on the two ends at once. For those, don't march from one side. Put one finger on the first slot and one on the last, and step them toward each other until they meet.

Reversing a list is the cleanest case to watch it work. Swap the two ends, then step both fingers inward. When they meet in the middle you're done. You've touched each slot exactly once and never allocated a second array.

def reverse(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:                    # stop the instant they meet
        a[lo], a[hi] = a[hi], a[lo]   # swap the two ends in one statement
        lo += 1; hi -= 1              # step both pointers inward
    return a

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:            # a single mismatch settles it — bail early
            return False
        lo += 1; hi -= 1
    return True

print("".join(reverse(list("REWARD"))))   # DRAWER   (3 swaps for 6 letters)
print(is_palindrome("racecar"))           # True
print(is_palindrome("python"))            # False

Read reverse line by line. lo, hi start at the two ends. The while lo < hi guard is the whole trick: the loop runs only while the fingers haven't crossed. Each pass swaps the pair they point at and pulls both inward by one. For 6 letters that's 3 swaps (I ran it: REWARD → DRAWER); for n items it's exactly n // 2 swaps. Count the operations: one loop, running n/2 times, with constant work inside. That's O(n) time. And crucially, O(1) extra space — no copy, no second array. is_palindrome is the same skeleton with a comparison instead of a swap, and it can bail early the moment two ends disagree.

Both-ends only helps when you act on both ends. But watch what happens when we point those two fingers at a sorted array and go hunting for a pair. →

02When it's sorted, every look kills half the mistakes

Here's the classic: find two numbers in an array that add up to a target. The brute force is two nested loops that try every pair — n(n-1)/2 comparisons, O(n²). In the hashing chapter we crushed it to O(n) with a hash "seen" set. But that costs O(n) extra space, and it works on any order. If the array is already sorted, two pointers do it in O(n) time and O(1) space — no hash at all.

Put lo at the smallest value, hi at the largest, and look at their sum. Here's the key step: because the array is sorted, that one comparison tells you exactly which pointer to move.

• If a[lo] + a[hi] is too small, no pair using a[lo] can ever reach the target — a[hi] is already the biggest partner available, and it wasn't enough. So a[lo] is hopeless: drop it, lo += 1.
• If the sum is too big, by the same logic a[hi] is hopeless with every remaining partner: drop it, hi -= 1.
• If it's equal, you found the pair.

Every step permanently eliminates one number from all its remaining pairings — a whole row (or column) of that n² grid of pairs, gone. There are only n numbers to eliminate, so the pointers meet in at most n − 1 steps.

def two_sum_sorted(a, target):        # a is sorted ascending
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return lo, hi             # found it
        elif s < target:
            lo += 1                    # too small -> raise the low end
        else:
            hi -= 1                    # too big  -> lower the high end
    return None

a = [2, 7, 11, 15, 20, 24, 40]
print(two_sum_sorted(a, 26))          # (0, 5)  ->  2 + 24 = 26,  found in 2 steps

I instrumented both versions. On that little array the two-pointer walk found 2 + 24 = 26 in 2 steps. On a sorted array of 100,000 numbers it found a middle pair in 11,232 steps, comfortably under the n − 1 = 99,999 ceiling. The brute force would have needed up to n(n−1)/2 ≈ 5,000,000,000 comparisons. Five billion versus eleven thousand, from the same data, just by letting sortedness do the eliminating.

The same "move the pointer that can't possibly help" idea powers container with most water: given wall heights, pick the two walls that hold the most water. Start wide, and always move the shorter wall inward. Moving the taller one can only shrink the width without lifting the limiting height. I ran it on [1,8,6,2,5,4,8,3,7] → max area 49, in a single O(n) pass.

So far the pointers move toward each other. Now aim them the same way — one leading, one trailing — and the gap between them becomes a window you drag across the data. →

03The sliding window: never recompute the overlap

New problem: in an array of numbers, find the largest sum of any k consecutive elements. The obvious approach is, for each starting position, add up its k elements and keep the best. There are n − k + 1 windows and each costs k − 1 additions, so the total is (n − k + 1)(k − 1) — roughly n·k, which is O(n²) when k grows with n. I ran it for n = 1000, k = 100: 89,199 additions.

Now look at two neighbouring windows. They overlap in k − 1 elements — almost everything. The brute force re-adds that shared middle every single time. That re-adding is the wasted work. So cut it: when the window slides one step right, the new sum is just the old sum, minus the element that fell off the left, plus the element that entered on the right. One subtraction, one addition — exactly 2 operations per step, no matter how big k is.

def max_window(a, k):
    s = sum(a[:k])              # first window: k-1 additions, paid once
    best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]    # +entering, -leaving : exactly 2 ops, any k
        if s > best:
            best = s
    return best

Line by line: sum(a[:k]) pays for the first window one time. Then r walks the entering index across the rest of the array. The single line s += a[r] - a[r-k] is the entire idea. a[r] joins, a[r-k] (exactly k slots back, the one falling off the left) leaves, and s is patched in O(1). There's no inner loop. Total work is (k − 1) for the first window plus 2 per slide — about 2n, which is O(n). I ran it against the brute force: same answer, but 1,899 additions instead of 89,199, 47× fewer. On a bigger case (n = 200,000, k = 1000) the wall-clock was roughly 0.66 s → 0.014 s, about 46× faster on this machine (timings vary by hardware, but the shape doesn't).

Fixed-size windows are the easy half. The real power shows up when the window has to breathe — growing and shrinking on its own to keep some rule true. →

04A window that breathes — grow right, shrink left

Problem: find the length of the longest substring with no repeated character. The window here isn't a fixed size. It's defined by an invariant: "the characters inside are all distinct." Keep two pointers, left and right. Push right forward to grow the window. The moment the new character is already inside, the invariant breaks, so pull left forward until it holds again. At every step, the window is the longest valid one ending at right. Track the best length you ever see.

def longest_unique(s):
    last = {}                        # char -> most recent index it appeared
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1      # jump left PAST the earlier copy, in one move
        last[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))    # 3   ("abc")
print(longest_unique("playlist"))    # 6   ("aylist")

Walk it: last remembers where each character was seen (a hash — the hashing chapter never really leaves you). For each new ch at index right, if we've seen it and its last position is inside the current window (>= left), we jump left to just past that old copy. That restores "all distinct" in a single move rather than stepping one at a time. Then we record ch's new position and update best. I ran it: "abcabcbb" → 3, and our running example "playlist" → 6 (the window "aylist", after the repeated l forces left forward).

Longest-valid grows greedily and shrinks only when forced. Flip the goal — find the smallest window that satisfies a condition — and the window learns a second move: squeeze. →

05The minimum window — cover, then squeeze

The hardest classic in the family: given a text and a set of characters you need, find the smallest slice of the text that contains all of them. Think "shortest stretch of a log that mentions all three error codes." The window now alternates between two phases. First expand right until the window covers everything needed. Then squeeze left as far as it can while staying covered, recording the smallest covered window each time, until it's no longer covered — then expand again.

The invariant tracker is a single counter, missing: how many needed characters are still uncovered. It updates in O(1) as characters enter and leave, so we always know the moment coverage flips. There's no rescanning the window to check.

from collections import Counter

def min_window(text, need):
    want = Counter(need)               # how many of each char we still want
    missing = len(need)                # total chars still uncovered
    left = 0
    best = ""
    for right, ch in enumerate(text):
        if want[ch] > 0:               # this char was actually needed
            missing -= 1
        want[ch] -= 1                  # may go negative: a surplus copy
        while missing == 0:            # covered! squeeze from the left
            if best == "" or right - left + 1 < len(best):
                best = text[left:right + 1]
            want[text[left]] += 1
            if want[text[left]] > 0:   # we just dropped a NEEDED char
                missing += 1           # uncovered again -> stop squeezing
            left += 1
    return best

print(min_window("ADOBECODEBANC", "ABC"))   # 'BANC'

The heart is the two counters. want[ch] tracks how many of each character the window still needs; it goes negative for surplus copies, which is what lets the squeeze phase know a character is expendable. missing hits 0 exactly when the window first covers the target. That's the trigger for the inner while, which shrinks from the left. Each time, it checks whether this is the smallest covered window yet, and it stops the instant it drops a genuinely needed character (want[...] > 0 after adding it back). I ran it on the textbook input "ADOBECODEBANC" needing "ABC" → 'BANC', the shortest slice holding an A, a B, and a C. Same total-travel argument as before: both pointers only move forward, so it's O(text length), not O(n²).

06The one move: reuse the overlap

There is, and it's the whole point of the chapter. A brute-force nested loop restarts its inner work from scratch at every outer step — re-summing an overlap, re-scanning for a partner, re-checking a window it just checked. But consecutive states of a scan overlap almost completely. The move that separates a coder from an engineer is to compute the change between states, not each state from zero. Two pointers and the sliding window are just the array-shaped version of that one reflex: don't restart — update.

This reflex earns its keep far past interview arrays. Finance: a rolling volatility or a moving-average crossover is a sliding window over a price stream. Recomputing the whole trailing average on every tick would be O(n·window); the delta update is O(1). Networking: TCP's window is why the internet doesn't melt under its own bookkeeping. Video codecs encode each frame as the difference from the last, not the whole picture again — the same "store the change" instinct at 30 frames a second. Rate limiters guarding every serious API are sliding windows of timestamps. Even your eyes, reading this line, drag a small focus window across the text rather than re-photographing the page for each word.

The everyday transfer is real too. To answer "what changed in this document?" you don't re-read it top to bottom — you track the delta. When a list is sorted, you rarely need to inspect everything. You can walk from the ends and let the ordering rule out whole regions, the way binary search bisects a bug. That is two-pointer thinking off the screen: let structure do the discarding, and never redo work you can update.

Every technique so far has been careful — reuse the overlap, restore the invariant, discard the impossible. The next chapter gets reckless on purpose: grab the best-looking option in front of you right now and never look back. It sounds like a way to be wrong — so when does that greedy gamble actually hand you the optimal answer, and when does it quietly betray you? →