Two Pointers and Sliding Window: The First Pattern

Put one finger on each end of this array:

[ 2, 7, 11, 15, 19, 23, 30, 35 ]      target: 41
  ^                            ^
  left                         right

Eight numbers, already sorted. The job: find two of them that add up to exactly 41. Your left finger is on the 2, your right finger is on the 35. Add them: 37. Too small, so move the left finger forward one. 7 + 35 = 42. Too big, so move the right finger back one. 7 + 30 = 37. Too small, left forward again. 11 + 30 = 41. Found it. Four moves.

Eight numbers make 28 possible pairs, and we checked 4 of them. The last lesson ended with the structures built and a promise to make them dance; that was the dance. Two fingers walking one array in choreography. The question this whole lesson hangs on is the one you should be asking right now: how did four moves get away with never looking at the other 24 pairs?

A pattern, not a structure

First, name what kind of thing this lesson even is, because it's new. Lessons 1 through 6 built and priced structures: things that hold data, with contracts and costs. This lesson builds nothing. It teaches a pattern: a reusable move that works across many problems, the way a chess tactic works across many games. You can't import a pattern. You recognize a situation, and the move plays itself.

The situation, here, is the most common slow shape in programming. The obvious solution to pair-sum looks like this:

function pair_sum_naive(items, target):
    for i from 0 to n-1:
        for j from i+1 to n-1:
            if items[i] + items[j] == target:
                return (i, j)
    return not_found

For every element, scan everything after it. It's has_duplicate from lesson 1 wearing a different shirt: n²/2 pairs, and at a million elements the wall-time table priced that shape at about 2.8 hours where a linear pass costs about 10 milliseconds. The pattern's promise is to take problems with that shape and collapse them into one pass, using nothing but two indices that move forward.

function pair_sum_sorted(items, target):
    left = 0
    right = n - 1
    while left < right:
        sum = items[left] + items[right]
        if sum == target: return (left, right)
        if sum < target:  left = left + 1     # items[left] is out of the game
        else:             right = right - 1   # items[right] is out of the game
    return not_found

The loop runs at most n times, because every iteration moves one of the two pointers inward and they start n apart. O(n) time, O(1) space, no allocation at all. The mystery is not the speed; it's the legality. Each step skips an entire column of pairs the naive version would have checked. Why is that safe?

Why throwing away is legal

Replay the first step slowly. Left is on 2, right is on 35, and 2 + 35 = 37 is too small. The lazy reading is "this pair fails, try another". The correct reading is much stronger.

The array is sorted, so 35, the element under the right pointer, is the largest candidate still in play. If 2 plus the largest available partner is still too small, then 2 plus any other partner is smaller still. The 2 cannot be part of the answer, paired with anything. Not "this pair fails": this element fails, with everyone. So we retire it, permanently, by moving left forward, and we never look back.

The mirror argument runs on the other side. When 7 + 35 = 42 came up too big: 7 is the smallest candidate still in play, and if 35 plus the smallest available partner is already too big, 35 is too big with everyone. Retire it, move right inward, never look back.

That's the whole trick, and it's worth saying in one sentence because it generalizes far beyond pair-sum: sortedness lets one comparison eliminate an entire region of the search space, not just one candidate. Each comparison permanently retires one element, n elements means at most n comparisons, and the 24 unchecked pairs were never skipped recklessly. Each one was proven irrelevant by some earlier comparison. Hold onto that idea of discarding a region per comparison; the next lesson is built entirely out of its most extreme form.

The family resemblance: never backward

Pair-sum is one member of a family, and before meeting the others it pays to name what they share, because this is the part that transfers to problems you haven't seen.

Every pattern in this lesson is fast for the same underlying reason: there is an argument why a pointer never needs to move backward. For the converging pair, the argument is sortedness. For the patterns coming up it will be different facts. But the arithmetic at the end is always the same: a pointer that only moves forward over n elements moves at most n times, so two of them do at most 2n total work, no matter how tangled the control flow around them looks. When you face a new problem, the question to ask is never "can I use two pointers here?". It's "is there a reason a pointer would never need to go back?". Find the reason and the O(n) follows. Fail to find one and the pattern doesn't apply, no matter how much you want it to.

There's a hardware bonus stacked on top, and lesson 2 already paid for it: two pointers marching forward are two sequential scans. Every cache line gets fully used, the prefetcher sees both streams and runs ahead of them, and the array does what arrays do best. The pattern wins twice: asymptotically fewer steps, and each step physically cheaper. Compare that with the naive nested loop, which re-walks the same region over and over, doing more steps and trashing more cache.

The rest of the lesson is that table, row by row.

Reader and writer: compaction in seven elements

Second geometry: both pointers start at the same end and move the same direction, at different rates. The classic job: remove duplicates from a sorted array, in place, no second array allowed.

The cast: a reader that scans every element, and a writer that lags behind, marking the end of the cleaned-up region. The reader's job is to find things worth keeping; the writer's job is to know where the next keeper goes.

function dedupe_sorted(items):
    if n == 0: return 0
    write = 1
    for read from 1 to n-1:
        if items[read] != items[write - 1]:
            items[write] = items[read]
            write = write + 1
    return write        # the first `write` slots are the answer

Walk it on [3, 3, 5, 7, 7, 7, 9]. The first element keeps itself, so both pointers start past it, at index 1. Reader sees 3, same as the last thing written: skip, writer stays. Reader sees 5, new: write it at slot 1, writer advances to 2. Reader sees 7, new: write at slot 2. Reader sees 7, then 7 again: skips. Reader sees 9: write at slot 3. Done, write is 4, and the front of the array reads [3, 5, 7, 9]. One pass, zero extra memory, and the array was repaired underneath the reader as it ran, which is safe for exactly one reason: the writer can never overtake the reader, so it only ever overwrites slots the reader has already left behind. Everything behind the writer is final. That's this row's never-backward argument.

If this feels like a niche interview move, it isn't. It is compaction, one of the most load-bearing loops in systems software. Kafka's log compaction walks a partition keeping only the newest record per key: reader scans, writer squeezes the survivors together. Compacting garbage collectors slide live objects toward one end of the heap to turn freed scraps into one contiguous block: writer chasing reader. Disk defragmentation, the same. Anywhere you hear "compaction", a writer is trailing a reader through a buffer, and you now know the whole algorithm.

Fast and slow: two runners on a track

Third geometry, and a debt to pay. Lesson 5 left one sentence dangling: a linked list with a cycle traverses forever, and detecting one cheaply was promised to this lesson.

The setup: somewhere in a long chain of nodes, a next pointer might point backwards to an earlier node. Follow the chain naively and you'll loop forever without ever knowing it. The obvious fix is a set of every node address seen so far, but that's O(n) memory for what feels like it should be a yes/no question.

Floyd's answer uses two pointers at different speeds: a slow pointer that advances one node per step, and a fast one that advances two. Picture two runners. On a straight track, the fast runner simply reaches the end first: if fast hits null, there is no cycle, done. But if the track loops, the fast runner enters the loop, comes around, and starts gaining on the slow one from behind. Once both are inside the loop, the gap between them shrinks by exactly one node per step (slow moves one, fast moves two, net closure one). A shrinking gap on a closed loop has nowhere to hide: it hits zero. The pointers collide, and a collision is proof of a cycle. O(n) time, two pointers of memory, no marking, no set.

Notice this row's never-backward argument is the strangest one: neither runner ever rewinds, and the proof doesn't track positions at all, only the gap, which moves in one direction just like a pointer does.

The same trick, with the finish line moved, finds the middle of a list in one pass: run fast and slow together, and when fast reaches the end, slow is standing on the midpoint, because it has taken exactly half as many steps. No length counter, no second pass.

Production cares about this more than it lets on. A cycle in a list that's supposed to be a chain is corruption: a bug wrote a next pointer it shouldn't have, and the symptom is a thread spinning forever at 100% CPU. Runtime checkers and debug allocators run exactly this detector, because it answers "is this structure broken?" without allocating anything in a context where the heap itself might be the broken thing.

The sliding window

The second half of the lesson is the fourth row of the table, and it's big enough to earn its own name. A window is two pointers with a particular contract: left and right bracket a contiguous run of the data, and the run itself is the object of interest, not the elements under the fingers.

Start with the simple flavor: the window has a fixed size k. The job: the sum (or average) of every run of 3 consecutive readings in [4, 2, 9, 7, 1]. The naive way recomputes each sum from scratch: 4+2+9 = 15, then 2+9+7 = 18, then 9+7+1 = 17. That's k additions per window, n windows, O(nk), and for a dashboard averaging the last minute of per-second latency samples, k is 60 and you're doing 60x the work you need to.

Look at two adjacent sums instead. The window [4, 2, 9] and the window [2, 9, 7] share almost everything: one element left (the 4), one element entered (the 7). So: 15 - 4 + 7 = 18. Then 18 - 2 + 1 = 17. Slide, subtract the leaver, add the enterer. Two operations per step regardless of k, O(n) total, and nothing inside the window is ever touched again. Every moving average on every monitoring dashboard you've ever looked at is this loop: enter, leave, never recompute.

Grow right, shrink left

The interesting problems don't fix k; they make the window earn its size. The marquee example: the shortest run of consecutive elements whose sum reaches a target. Concretely: in [2, 3, 1, 2, 4, 3], find the shortest contiguous run summing to at least 7.

Two rules, one for each pointer:

• right moves forward to grow the window until the condition holds (sum ≥ 7).
• While the condition holds, record the window's length, then move left forward to shrink it, hunting for a smaller window that still qualifies.

function min_subarray_len(items, target):
    left = 0
    sum = 0
    best = infinity
    for right from 0 to n-1:
        sum = sum + items[right]            # grow
        while sum >= target:                # shrink while still valid
            best = min(best, right - left + 1)
            sum = sum - items[left]
            left = left + 1
    return 0 if best == infinity else best

Walk the whole thing on [2, 3, 1, 2, 4, 3], target 7:

Answer: 2, the run [4, 3]. The window breathes: it inflates until it's valid, exhales until it isn't, and the best answer is always caught at the moment of minimal validity.

Why the nested-looking loop is still O(n)

Look back at that pseudocode and notice something alarming: there is a while loop inside a for loop. Six lessons of training scream quadratic. The shape of the code is lying to you, and learning to see through this particular lie is half the value of the lesson.

Don't count iterations of loops; count moves of pointers. right moves forward exactly n times over the whole run, once per for iteration. left only ever moves forward, and it can never pass right, so across the entire execution, all those inner while iterations combined, it moves at most n times. Total pointer moves: at most 2n. Some individual for iterations do lots of shrinking and some do none, but the budget is global, and it's linear. This is the same accounting trick as lesson 1's amortized analysis: price the whole sequence, not the worst step.

And the never-backward argument that licenses it: the sum of a window of non-negative numbers is monotonic in its edges. Growing the window can only raise the sum, shrinking can only lower it. So once left has moved past a position, no future answer could need it back: a longer window ending further right that re-included it would be re-examining a superset of something already measured. (Mind the fine print: with negative numbers in the array, that monotonicity dies, the discard argument dies with it, and this exact pattern stops being correct. Patterns have preconditions; checking them is the skill.)

One more famous member of the same family, same skeleton, different condition: longest substring without repeating characters. Grow right over the string; the window's invariant is "no duplicates inside". When the entering character is already in the window, shrink left past its previous occurrence. The membership check wants the seen-set from lesson 1's duplicate-checker, and the full machinery behind that set arrives in lesson 12, but the window logic is identical: grow, violate, shrink, record.

Where windows run production

The window pattern is unusual among interview staples in that production uses it under the same name.

• Rate limiting. The algorithm called "sliding window rate limiting" in every API gateway's documentation is literally this lesson: count the requests in the last 60 seconds, where each new request enters the window and old ones fall out the back. Whether the gateway keeps actual timestamps or the cheaper counter approximation, the mental model it implements is a window sliding over a request stream.
• TCP. The flow-control mechanism in the protocol moving these very bytes is named the sliding window: a span of bytes the sender is allowed to have in flight, whose left edge advances as the receiver acknowledges data. One beat of recognition is all this needs, but the name is no coincidence; it's the same idea operating on the same invariant.
• Stream analytics. Moving averages, rolling p99s, "errors in the last 5 minutes" alerts: every one is a fixed-size window with enter/leave bookkeeping instead of recomputation, because the dashboard repaints every second and can't afford to re-sum a minute of samples each time.

One honest scope note. Lesson 6 teased the sliding window maximum: a window gliding over data, reporting the largest element inside at every position. That problem looks like it belongs here, and it doesn't, for an instructive reason: when the maximum falls out the left edge, a plain window has no idea what the new maximum is without rescanning. Sums subtract cleanly; maximums don't. Fixing that takes a smarter window, the monotonic deque built on lesson 6's chunked-array deque, and it lives in part two of this course, dsa-patterns, where the pattern family gets its full treatment.

The two moves, in real code

The videos stay in pseudocode; here are the two marquee algorithms in the three languages this course carries.

function pairSumSorted(items: number[], target: number): [number, number] | null {
  let left = 0
  let right = items.length - 1
  while (left < right) {
    const sum = items[left] + items[right]
    if (sum === target) return [left, right]
    if (sum < target) left++ // items[left] can't pair with anyone
    else right-- // items[right] can't pair with anyone
  }
  return null
}
 
function minSubarrayLen(items: number[], target: number): number {
  let left = 0
  let sum = 0
  let best = Infinity
  for (let right = 0; right < items.length; right++) {
    sum += items[right] // grow
    while (sum >= target) {
      best = Math.min(best, right - left + 1)
      sum -= items[left] // shrink
      left++
    }
  }
  return best === Infinity ? 0 : best
}

func pairSumSorted(items []int, target int) (int, int, bool) {
	left, right := 0, len(items)-1
	for left < right {
		sum := items[left] + items[right]
		switch {
		case sum == target:
			return left, right, true
		case sum < target:
			left++ // items[left] can't pair with anyone
		default:
			right-- // items[right] can't pair with anyone
		}
	}
	return 0, 0, false
}
 
func minSubarrayLen(items []int, target int) int {
	left, sum, best := 0, 0, len(items)+1
	for right := 0; right < len(items); right++ {
		sum += items[right] // grow
		for sum >= target {
			if w := right - left + 1; w < best {
				best = w
			}
			sum -= items[left] // shrink
			left++
		}
	}
	if best == len(items)+1 {
		return 0
	}
	return best
}

std::optional<std::pair<int, int>> pair_sum_sorted(const std::vector<int>& items, int target) {
    int left = 0;
    int right = static_cast<int>(items.size()) - 1;
    while (left < right) {
        int sum = items[left] + items[right];
        if (sum == target) return std::pair{left, right};
        if (sum < target) ++left;   // items[left] can't pair with anyone
        else --right;               // items[right] can't pair with anyone
    }
    return std::nullopt;
}
 
int min_subarray_len(const std::vector<int>& items, int target) {
    int left = 0;
    long long sum = 0;
    int best = std::numeric_limits<int>::max();
    for (int right = 0; right < static_cast<int>(items.size()); ++right) {
        sum += items[right];        // grow
        while (sum >= target) {     // shrink while still valid
            best = std::min(best, right - left + 1);
            sum -= items[left];
            ++left;
        }
    }
    return best == std::numeric_limits<int>::max() ? 0 : best;
}

Walk the load-bearing lines, because they're the same three lines in all nine functions. In pairSumSorted, the entire algorithm is the two-way branch: sum < target retires the left element, anything else retires the right, and the comment on each line is the proof from earlier in the lesson, compressed. The loop condition left < right is the budget: the pointers start at opposite ends and every iteration closes the gap by one, so the loop body is the whole O(n) bound made visible. In minSubarrayLen, the for advances right, full stop; the inner while advances left, full stop; neither line ever decrements anything, which is the never-backward invariant written in code you can grep for. Two language notes worth a glance: the Go version signals not-found with a third return value because Go has no Optional, and the C++ version accumulates into a long long because a window of large ints can overflow the sum even when each element fits, the kind of edge that pseudocode hides and production doesn't.

One move, four costumes

So, the first pattern, and the shape of every pattern to come. Nothing was built today; a move was installed. Where a structure is something you hold, a pattern is something you see: a nested loop re-scanning a region, and behind it, some reason, sortedness, finality behind a writer, a shrinking gap, a monotonic sum, why one pass was enough all along. Four costumes, one move: find the reason a pointer never goes back, and the O(n²) collapses.

And one of those costumes is hiding something bigger. The converging pair won by discarding a region per comparison: one element gone, every step, guaranteed. Next lesson takes that idea to its logical extreme: what if each comparison could discard half of everything that remains? That's binary search, the most famous algorithm in computer science, the log n rung from lesson 1's ladder finally cashed in, and it is notoriously easy to implement wrong. One template handles every variant of it. See you there.