Two Pointers & the Sliding Window

You've got a sorted list of prices and you want to know if any two of them add up to exactly what's in your wallet. The obvious move is to try every pair: take the first price, check it against all the others, then the second against all the others, and so on. That works. It's also O(n²). For a list of ten thousand prices, that's a hundred million comparisons for a question you can answer in one clean sweep.

Two patterns kill that kind of waste. Both walk an array with a small number of moving indices instead of nested loops, and both drop you from quadratic time to linear. Learn them once and you'll spot them in problem after problem.

The brute force you're escaping

Here's the pair-sum problem written the slow way, so you can feel what you're replacing:

def has_pair(prices, target):
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            if prices[i] + prices[j] == target:
                return True
    return False

Two nested loops. Every element gets checked against every later element. The work grows with the square of the input. The whole trick of the two-pointer pattern is realizing that if the list is sorted, you don't need both of those loops.

Two pointers: close in from both ends

Put one pointer at the start (the smallest value) and one at the end (the largest). Add what they point at. If the sum is too big, the only way to shrink it is to move the right pointer left to a smaller number. If the sum is too small, move the left pointer right to a bigger one. Either way, one pointer moves each step, so you sweep the whole array exactly once.

Watch it run. Drag through and notice how the two ends march toward each other, never backtracking:

The sorted order is what makes this honest. Because values only grow left to right, a sum that's too high can only be fixed by pulling the right pointer in, and a sum that's too low can only be fixed by pushing the left pointer out. There's never any doubt about which one to move, so you never have to reconsider a position. One pass, no nesting.

Sliding window: a frame that slides

The two-pointer pattern shines when the array is sorted and you're hunting for a pair. The sliding window is its cousin for a different shape of question: "what's the best run of k consecutive elements?" Max sum, longest substring without repeats, that family.

The naive version recomputes the sum of every window from scratch, which is O(n·k). The window trick keeps a running total instead. Slide one step right: add the element entering on the right, subtract the one falling off the left. The sum updates in constant time per step.

See how the frame never recomputes the whole block. It just adds one and drops one as it slides. That's the entire idea: maintain the answer for the current window cheaply, then nudge the window along.

Both patterns in runnable Python

Here are clean implementations of both. Run it, then change the array or the target and run again. The answers update live:

Notice neither function has a nested loop over the input. two_sum_sorted moves left and right toward each other, so together they take at most n steps. max_window_sum does one setup sum plus a single pass. Both are O(n).

These build directly on the basics from the Python series. If while loops and indexing feel shaky, the loops lesson is worth a quick reread, and the pointer-walking logic is just Python functions doing bookkeeping with a couple of variables.

Where this leaves you

Two pointers and the sliding window are the same instinct wearing two outfits: instead of nesting a loop inside a loop, move a small number of indices across the data once and maintain just enough state to answer the question. Spot a "find a pair in a sorted array" or a "best run of k in a row" and you've already got the O(n) answer.

Next we go from indices walking sideways to functions calling themselves. Next: Recursion & the Call Stack.