38Two pointers & the sliding window

In Chapter 37 we bought O(1) lookups the honest way: a hash table, extra memory traded for speed. Here we chase that same collapse of a nested loop, but this time we pay nothing extra at all. The plan is two array patterns, back to back. First come two pointers that march in from both ends and let the data eliminate itself. Then comes a sliding window that patches its running answer as it moves instead of rebuilding it from scratch. The whole 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, on sight, whether it's secretly a single sweep in disguise. And you'll know exactly how to set it free.

01Two fingers, marching inward

Let's start with the array you already know from Volume 1. It's 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: the answer depends on the two ends at once. For those, don't march in from one side. Put one finger on the first slot and one on the last, then step them toward each other until they meet.

One quick demystification before we go further, because the word "pointer" scares people who have heard C stories. A pointer here is nothing but a plain Python int sitting in a variable, holding an index. There's no address arithmetic, no memory magic, nothing you can dereference by accident. When we say "move the pointer," we mean lo += 1, an integer getting bigger by one. That's the whole machinery, and it's why the pattern costs O(1) extra space: two integers are all the state we carry, no matter how big the array grows. Keep the contrast with Chapter 37 in view as we go, too. The hash bought speed by spending memory, while this chapter buys speed by exploiting structure the data already has.

Reversing a list is the cleanest place to watch the pattern earn its keep. Swap the pair of values under the two fingers, then step both fingers one slot inward. When the fingers meet in the middle, the whole list is reversed and you're done. You've touched each slot exactly once, and you 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, 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.

Watch the early bail pay off. Run is_palindrome on REWARD: the very first comparison puts R against D, they disagree, and we return False after a single check — the other four letters never get looked at. Now run it on RACECAR: R=R, then A=A, then C=C, the fingers meet on the middle E, and it returns True after exactly 3 comparisons — that's n // 2 for 7 letters. A real palindrome pays the full n // 2; a mismatch usually pays far less, because it stops the instant 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 tries every pair with two nested loops, which costs n(n-1)/2 comparisons — O(n²). In the hashing chapter we crushed that to O(n) with a hash "seen" set. But the set costs O(n) extra space, and its one real virtue is that it works on any order. If the array is already sorted, two pointers do the job in O(n) time and O(1) space, with no hash at all.

It helps to see what the brute force is actually walking. Picture every candidate pair laid out as a grid, one row per choice of the first number, one column per choice of the second. An array of n values gives roughly n²/2 distinct pairs to try, and the nested loops grind through them one at a time. For n = 100,000 that is about five billion pairs. Hold that picture, because the sorted version is about to delete it a whole row at a time.

Put lo on the smallest value and hi on the largest, then look at their sum. Now comes the magic, and I want you to savour it, because this is the whole pattern. Since the array is sorted, that one comparison tells you exactly which pointer to move.

Here's the rule, and you can check it on your fingers. If the sum is too big, the only way down is to shrink the large side, so pull hi inward. If the sum is too small, the only way up is to grow the small side, so push lo forward. Try it with a target of 26 when the fingers read 2 and 40. The sum is 42, an overshoot. Now notice the stronger fact: 2 is the smallest value in the array, so 40 plus anything here overshoots. That means 40 can never be part of any answer, and pulling hi in discards it for good. One comparison has eliminated a number forever, and that's the engine of the whole walk.

• 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 single step permanently eliminates one number from all of its remaining pairings. That's a whole row, or a whole column, of the n² grid of candidate pairs, gone in one comparison. And since there are only n numbers to eliminate, the pointers must 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 to make this concrete. On that little array, the two-pointer walk found 2 + 24 = 26 in just 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 on that same array. 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 a row of wall heights, pick the two walls that hold the most water between them. Start with the widest span, then always move the shorter wall inward. Here's why: moving the taller wall can only shrink the width, and it can never lift the limiting height. I ran it on [1,8,6,2,5,4,8,3,7] and got a max area of 49 in a single O(n) pass.

Let's do the area arithmetic, because it's the whole reason the rule is safe. Water trapped between two walls is width × the shorter of the two heights — the taller wall just spills over the short one, so the short wall caps the fill. Start at the full span of [1,8,6,2,5,4,8,3,7]: the ends are height 1 and height 7, width 8, so area = 8 × min(1,7) = 8. That left wall of height 1 is the limit. Moving the tall wall inward can only shrink the width while the 1 still caps the height, so it's pure loss — that's why we move the short wall. Do that until the ends read height 8 and height 7 with width 7: area = 7 × min(8,7) = 49, exactly the max the code reported.

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 to take each starting position, add up its k elements, and keep the best. There are n − k + 1 windows, and each one costs k − 1 additions to sum. So the total is (n − k + 1)(k − 1), which is roughly n·k, and that's O(n²) when k grows with n. I ran it for n = 1000 and k = 100 and counted 89,199 additions.

Make it tiny enough to check by hand. Take a = [4, 2, 9, 7, 1] with k = 3. The windows are 4+2+9 = 15, then 2+9+7 = 18, then 9+7+1 = 17, so the best is 18. That's n − k + 1 = 3 windows at k − 1 = 2 additions each, 6 additions in total. Six is nothing, but the cost scales as the product n·k, and products of growing things are exactly what this volume has taught us to fear.

Now stare at two neighbouring windows, because the waste is hiding in plain sight there. They overlap in k − 1 elements, which is almost everything either window contains. The brute force re-adds that whole shared middle every single time it moves one step. That re-adding is the wasted work. Kill 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 and one addition — exactly 2 operations per step, no matter how big k is.

Run the delta on that same tiny array and watch it agree. The first window costs its full price: 4+2+9 = 15. To slide, drop the 4 that left and add the 7 that entered: 15 − 4 + 7 = 18. Slide again, drop the 2 and add the 1: 18 − 2 + 1 = 17. Those are the same three sums the brute force produced, but each slide cost 2 operations instead of a fresh re-sum — and if k were 1000, a slide would still cost exactly 2.

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

Let's read it line by line, starting with sum(a[:k]), which pays for the first window exactly 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 the window, a[r-k] leaves it, and s is patched in O(1). The leaving element sits exactly k slots back, so it's always the one falling off the left. There is no inner loop anywhere, so the total work is (k − 1) additions for the first window plus 2 per slide — about 2n, which is O(n). I ran it against the brute force and got the same answer from 1,899 additions instead of 89,199 — 47× fewer. On a bigger case, n = 200,000 with k = 1000, the wall-clock went from 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

Here's the next problem: find the length of the longest substring with no repeated character. This window isn't a fixed size like the last one was. It's defined by an invariant instead, a condition we promise to keep true: "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, so 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")

Let's walk the code. last remembers the index where each character was last seen — a hash, because the hashing chapter never really leaves you. For each new ch at index right, we check whether we've seen it before. If 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 one slot at a time. Then we record ch's new position and update best. I ran it: "abcabcbb" → 3, and our running example "playlist" → 6. That 6 is the window "aylist", found after the repeated l forces left forward.

Trace "playlist" by hand to feel that jump. The letters sit at indices 0–7: p l a y l i s t. right grows the window across p, l, a, y — all distinct, length 4 — until index 4 hands us a second l. Its last position was index 1, which is still inside the window, so left leaps from 0 straight to 2, one slot past that old l. Now the window is a, y, l, and it keeps growing through i, s, t with no further repeats, finishing as "aylist" at length 6. One clean jump, not four little single-slot steps — and that jump is the O(1) restore the last hash pays for.

Now pause on the cost, because this loop shape fools almost everyone at first. A left that moves inside a loop over right looks like a nested loop, and nested loops smell like O(n²). But count total travel instead of counting iterations. right moves forward n times over the whole run, and left only ever moves forward too, so it moves at most n times in total across every trigger combined. Total pointer travel is at most 2n moves, which is O(n). This style of counting has a name, amortized analysis: charge the work to the whole journey, not to the single step.

"""two_windows.py -- write both, then let a brute-force oracle grade you."""
import random, time

def max_window_sum(a, k):
    """Largest sum of k consecutive items, and the index that window starts at."""
    if k <= 0 or k > len(a):
        return None                       # no window of that size exists -- say so
    s = sum(a[:k])                        # pay for the first window once
    best, start = s, 0
    for r in range(k, len(a)):
        s += a[r] - a[r - k]              # +enterer, -leaver: 2 ops, whatever k is
        if s > best:
            best, start = s, r - k + 1
    return best, start

def longest_unique_substring(s):
    """Longest stretch with no repeated character -- a seen-set window that breathes."""
    seen, left, best, span = set(), 0, 0, ""
    for right, ch in enumerate(s):
        while ch in seen:                 # WHILE, not if: evict until the clash is gone
            seen.discard(s[left]); left += 1
        seen.add(ch)
        if right - left + 1 > best:
            best, span = right - left + 1, s[left:right + 1]
    return best, span

def max_window_brute(a, k):               # the oracle: obviously right, obviously slow
    if k <= 0 or k > len(a): return None
    sums = [sum(a[i:i + k]) for i in range(len(a) - k + 1)]
    return max(sums), sums.index(max(sums))

def longest_unique_brute(s):              # the oracle: every substring, checked
    best, span = 0, ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            piece = s[i:j + 1]
            if len(set(piece)) == len(piece) and len(piece) > best:
                best, span = len(piece), piece
    return best, span

print("max_window_sum([4, 2, 9, 7, 1], 3)  ->", max_window_sum([4, 2, 9, 7, 1], 3))
print("max_window_sum([1, 2], 5)           ->", max_window_sum([1, 2], 5))
print("longest_unique_substring('playlist')->", longest_unique_substring("playlist"))
print("longest_unique_substring('abcabcbb')->", longest_unique_substring("abcabcbb"))
print("longest_unique_substring('bbbb')    ->", longest_unique_substring("bbbb"))
print("longest_unique_substring('')        ->", longest_unique_substring(""))

random.seed(38)
for _ in range(3_000):                    # 3,000 random cases against both oracles
    a = [random.randrange(-9, 10) for _ in range(random.randint(1, 25))]
    k = random.randint(1, len(a))
    assert max_window_sum(a, k) == max_window_brute(a, k), (a, k)
    s = "".join(random.choice("abcd") for _ in range(random.randint(0, 20)))
    assert longest_unique_substring(s)[0] == longest_unique_brute(s)[0], s
print("\n3,000 random cases, both functions, 0 mismatches")

big = [random.randrange(1_000) for _ in range(200_000)]
for fn in (max_window_brute, max_window_sum):
    t0 = time.perf_counter(); r = fn(big, 1_000); dt = (time.perf_counter() - t0) * 1000
    print(f"  {fn.__name__:<16} n=200,000 k=1,000 -> {r}  {dt:>8.2f} ms")

text = "".join(random.choice("abcdefghij") for _ in range(200_000))
t0 = time.perf_counter(); n, _ = longest_unique_substring(text); dt = (time.perf_counter() - t0) * 1000
print(f"  longest_unique_substring on 200,000 characters -> {n}  {dt:>8.2f} ms  (one pass)")


# ---------- what it printed ----------
#
# max_window_sum([4, 2, 9, 7, 1], 3)  -> (18, 1)
# max_window_sum([1, 2], 5)           -> None
# longest_unique_substring('playlist')-> (6, 'aylist')
# longest_unique_substring('abcabcbb')-> (3, 'abc')
# longest_unique_substring('bbbb')    -> (1, 'b')
# longest_unique_substring('')        -> (0, '')
#
# 3,000 random cases, both functions, 0 mismatches
#   max_window_brute n=200,000 k=1,000 -> (529554, 162015)   1125.26 ms
#   max_window_sum   n=200,000 k=1,000 -> (529554, 162015)     17.00 ms
#   longest_unique_substring on 200,000 characters -> 10     32.99 ms  (one pass)
#
#
# ---------- the two questions ----------
#
# WHY IT IS NOT O(n^2).
#   Count total pointer TRAVEL, not nesting depth. `right` advances once per
#   character: n moves, full stop. `left` only ever moves forward, and it can
#   never pass `right`, so across the entire run it also moves at most n times.
#   Total <= 2n moves -> O(n). The inner while looks like a second loop, but it
#   is not paid per outer step -- it is paid once, spread over the whole
#   journey. That is amortized reasoning, and the giveaway is that neither
#   pointer ever moves backward. If `left` could reset to 0, this argument dies
#   and the loop really is quadratic.
#
# WHY THE 200,000-CHARACTER RUN ANSWERS 10.
#   The alphabet has ten letters, so no distinct stretch can be longer than 10 --
#   the eleventh character must repeat one of the first ten. The window is
#   bounded by the alphabet, not by the text. That is also why the timing stays
#   linear: the set never holds more than ten items.
#
# STEP-BY-STEP vs THE JUMP.
#   This version steps `left` one slot at a time and needs only a set. The
#   chapter's version keeps a dict of last positions and jumps `left` straight
#   past the old copy in a single assignment. Both are O(n) by the same travel
#   argument, and both do about the same total work. Prefer the JUMP when you
#   can compute the destination -- it is fewer operations and reads cleanly.
#   Prefer the STEP whenever the shrink target cannot be precomputed, which is
#   exactly the minimum-window problem in section 05: how far to squeeze depends
#   on a running coverage count you can only discover by stepping and watching
#   it flip.

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

Now 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 go while staying covered, recording the smallest covered window each time. When the squeeze finally drops coverage, go back to expanding, and repeat until the text runs out. Picture an inchworm moving along the text: the front end stretches forward, then the back end catches up.

The invariant tracker here is a single counter called missing, the count of needed characters still uncovered. It updates in O(1) every time a character enters or leaves the window. So we always know the exact moment coverage flips, without ever 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 of the code is the two counters. want[ch] tracks how many of each character the window still needs. It's allowed to go negative for surplus copies, and that negative is what tells the squeeze phase a character is expendable. missing hits 0 exactly when the window first covers the target. That zero is the trigger for the inner while, which shrinks the window from the left. Each shrink step checks whether this is the smallest covered window yet. The squeeze stops the instant it would drop a genuinely needed character, which shows up as want[...] > 0 after adding it back. I ran it on the textbook input "ADOBECODEBANC" needing "ABC" and got 'BANC', the shortest slice holding an A, a B, and a C. The cost argument is the same total-travel one as before. Both pointers only ever move forward, so the whole thing is O(text length), not O(n²).

Walk the missing counter on the textbook case: text "ADOBECODEBANC", needed set "ABC", so missing starts at 3. Expand right and watch it fall: the A at index 0 drops it to 2, the B at index 3 drops it to 1, and the C at index 5 drops it to 0. That zero is coverage for the first time, over the slice "ADOBEC" of length 6, and it fires the squeeze. Left and right keep breathing until the tightest covered slice surfaces: "BANC", length 4. Notice we never once rescanned the window to test coverage — a single counter, nudged by ±1 as characters cross the edges, told us the exact instant it flipped.

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 incarnation of that one reflex: don't restart — update.

So how do you actually spot one of these in the wild? Look at what the inner loop touches, and ask how much of it the previous outer step already touched. If the two workloads overlap heavily, say a shared sum or a shared stretch of text, the loop is a sweep in disguise. Then find the delta: what enters and what leaves. Ask what tiny record lets you patch the answer in O(1): a running sum, a counter, a hash of last positions. If the data is ordered, ask the other question too: does one comparison prove that some element can never matter again? A yes to either question is the moment O(n²) quietly becomes O(n).

you type
# ---------- windows.py ----------
import random, time

def moving_avg(a, k):                     # 1. FIXED: patch the sum, never rebuild it
    s, ops = sum(a[:k]), k - 1
    out = [s / k]
    for r in range(k, len(a)):
        s += a[r] - a[r - k]                # +enterer, -leaver: exactly 2 ops, any k
        ops += 2
        out.append(s / k)
    return out, ops

def moving_avg_brute(a, k):                 # the same answer, re-summing every window
    out = [sum(a[i:i + k]) / k for i in range(len(a) - k + 1)]
    return out, (len(a) - k + 1) * (k - 1)  # k-1 additions per window, every window

def longest_under(a, limit):                # 2. BREATHING: grow right, shrink left
    left, s, best, travel = 0, 0, 0, 0
    for right, x in enumerate(a):
        s += x; travel += 1                 # the enterer joins the state
        while s > limit and left <= right:  # while, not if: one enterer can evict several
            s -= a[left]; left += 1; travel += 1
        best = max(best, right - left + 1)
    return best, travel

def two_sum_sorted(a, target):              # 3. CONVERGING: the ends march inward
    lo, hi, ops = 0, len(a) - 1, 0
    while lo < hi:
        ops += 1
        s = a[lo] + a[hi]
        if s == target: return (lo, hi), ops
        if s < target: lo += 1
        else:          hi -= 1
    return None, ops

small = [4, 2, 9, 7, 1]                     # same three averages, two ways of paying
print("1. fixed window, k = 3, on", small)
for fn in (moving_avg_brute, moving_avg):
    out, ops = fn(small, 3)
    print(f"   {fn.__name__:<16} {[round(v, 2) for v in out]}  in {ops} additions")

random.seed(38)
big, k = [random.randrange(100) for _ in range(200_000)], 1_000
for fn in (moving_avg_brute, moving_avg):
    t0 = time.perf_counter(); out, ops = fn(big, k); dt = (time.perf_counter() - t0) * 1000
    print(f"   n=200,000 k=1,000  {fn.__name__:<16} {ops:>12,} ops  {dt:>9.2f} ms")

print("\n2. breathing window -- longest stretch summing to at most 15")
print("  ", longest_under([5, 1, 3, 8, 2, 1, 1, 9], 15), " <- (length, total pointer travel)")
worst = [1] * 50_000 + [10 ** 6]            # forces the window to collapse at the very end
best, travel = longest_under(worst, 10)
print(f"   n = {len(worst):,}: travel = {travel:,}, and the 2n ceiling is {2 * len(worst):,}")

print("\n3. converging pointers on a sorted array, target 26")
print("  ", two_sum_sorted([2, 7, 11, 15, 20, 24, 40], 26), " <- ((lo, hi), looks taken)")

$ python windows.py

you see
1. fixed window, k = 3, on [4, 2, 9, 7, 1]
   moving_avg_brute [5.0, 6.0, 5.67]  in 6 additions
   moving_avg       [5.0, 6.0, 5.67]  in 6 additions
   n=200,000 k=1,000  moving_avg_brute  198,801,999 ops     646.96 ms
   n=200,000 k=1,000  moving_avg            398,999 ops      23.61 ms

2. breathing window -- longest stretch summing to at most 15
   (5, 12)  <- (length, total pointer travel)
   n = 50,001: travel = 100,002, and the 2n ceiling is 100,002

3. converging pointers on a sorted array, target 26
   ((0, 5), 2)  <- ((lo, hi), looks taken)

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 cost O(n·window), while 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 frame, never the whole picture again — the same "store the change" instinct at 30 frames a second. Rate limiters guarding every serious API are sliding windows over timestamps. Even your eyes, reading this line, drag a small focus window across the text rather than re-photographing the page at every word.

The everyday transfer is real too. To answer "what changed in this document?" you don't re-read it from the top, you track the delta. When a list is sorted, you rarely need to inspect everything in it. You can walk in from the ends and let the ordering eliminate 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. Carry that reflex out of this chapter, because it will follow you into every system you ever profile.

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? →