18 MIN GUIDE · INTERMEDIATE · TWO POINTERS & SLIDING WINDOW

Two Pointers and Sliding Windows

Turn nested searches into linear scans by proving when a left or right boundary can move without losing a valid answer.

Two indices, one invariant

Two-pointer algorithms work when a comparison proves that one boundary can be discarded. Common layouts are:

opposing pointers on sorted data,
a fast pointer that reads and a slow pointer that writes,
a left and right edge enclosing a window.

The important step is not adding two variables; it is stating why the pointer you move can never be part of a better answer.

Opposing pointers

For a sorted pair-sum problem, a sum below the target cannot be improved by moving the right pointer left, because that only decreases the sum. Therefore move the left pointer right. The symmetric argument handles a sum above the target.

For container area, the shorter wall limits height. Moving the taller boundary reduces width without improving that limiting height, so only the shorter boundary is worth moving.

Fixed and variable windows

A fixed window of size k updates in O(1): add the entering value and remove the leaving one. A variable window expands until a condition is met and then shrinks while it remains valid.

Variable shrinking requires a monotonic property. With positive numbers, removing a left value can only reduce a sum. Negative values break that reasoning and often require prefix sums plus a deque or ordered structure.

Sorted pair example

a=[1,2,4,7,11]; target=9; l=0; r=len(a)-1
while a[l]+a[r] != target:
    if a[l]+a[r] < target: l += 1
    else: r -= 1
print(l, r)

Output

1 3

A reliable checklist

Define what the interval contains, what makes it valid, and which update restores validity. Prove that each pointer moves at most n times. Then test a one-element input, no valid answer, all-equal values, duplicates at both boundaries, and a result using the entire input.

Practice Three Sum, Minimum Size Subarray Sum, and Container With Most Water.