Two Pointers, Sliding Windows & Prefix Sums

We open a new module on sequences (arrays and strings), and the first thing to learn is a way of thinking that recurs everywhere in it. A great many array questions have an obvious brute-force answer that examines every pair or every subarray: two nested loops, $\Theta (n^2)$ work. The techniques in this lesson share a single trick for collapsing that quadratic scan into a single linear pass. Instead of re-examining the array from scratch at each step, we maintain a small amount of state (one or two indices, a window, a running sum) together with an invariant that this state always tells us something true. Each step advances an index and patches the invariant in $O(1)$, so the whole pass is $O(n)$.¹ The art is choosing the invariant. The loop-invariant discipline from our first algorithm, establish it, maintain it, read off the answer at termination, is exactly the reasoning we use to prove these correct.²

Two pointers, opposite ends

The cleanest instance lives on a sorted array. Suppose $a[0\dots n-1]$ is sorted ascending and we want indices $l<r$ with $a[l]+a[r]=T$ for a target $T$. Brute force tries all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. Instead, place one pointer at each end, $l=0$ and $r=n-1$, and let them converge:

At each step we look at $s=a[l]+a[r]$. If $s=T$ we are done. If $s<T$, then $a[l]$ paired with anything still available is too small. Since $a[l]+a[r]$ is the largest sum involving $a[l]$ in the window and it already fell short, $a[l]$ cannot be part of any solution, and we discard it by advancing $l$. The case $s>T$ is symmetric: $a[r]$ is too large to pair with anything remaining, so we drop it by decrementing $r$.

The pointers start $n-1$ apart and each step closes the gap by one, so the loop runs at most $n-1$ times: $O(n)$ time, $O(1)$ space. This is exactly Two Sum II on a sorted input, and the reason sorting first ($O(n\log n)$) can beat a hash table when the array is already sorted or space is tight.

The same converging-pointers move solves Container With Most Water: with heights $a[0\dots n-1]$, the area between walls $l$ and $r$ is $(r-l)\cdot \min (a[l],a[r])$. We start at the widest pair and always advance the pointer at the shorter wall. Moving the taller one can only shrink the width without ever raising the binding height, so it can never improve on the current best. The shorter wall, by contrast, might be replaced by a taller one. One pass, $O(n)$.

Two pointers, same direction (fast/slow)

A second flavor sends both pointers the same way at different speeds. The canonical use is rewriting an array in place: a write pointer $w$ trails a read pointer $r$, and $w$ only advances when $a[r]$ is an element we want to keep. To remove duplicates from a sorted array:

The read pointer scans every element once and the write pointer never overtakes it, so the routine is $O(n)$ time and $O(1)$ extra space; it overwrites the input rather than allocating output. The same trailing-write pattern underlies in-place partition (the core of quicksort and quickselect): a write pointer marks the boundary between elements already placed below the pivot and the rest.

Sliding windows

A window is a contiguous range $[l,r]$ that we slide rightward across the array while keeping it consistent with some property. Two regimes appear.

Fixed size $k$. To compute, say, every window's sum, we do not re-add $k$ elements each time. We add the entering element and subtract the leaving one: when the window advances from $[l,r]$ to $[l+1,r+1]$, update $\text{sum}+=a[r+1]-a[l]$. Each slide is $O(1)$, so all $n-k+1$ windows cost $O(n)$ total.

Variable size. Here the window grows and shrinks to stay feasible. The pattern: advance $r$ to expand the window greedily; whenever the window violates its constraint, advance $l$ to shrink it until the constraint holds again. The double loop looks $O(n^2)$, but it is not:

Worked: smallest subarray with sum $\ge S$. Given positive integers and a target $S$, find the shortest contiguous subarray whose sum is at least $S$ (Minimum Size Subarray Sum). Keep a running window sum; expand $r$ to grow it, and the moment the sum reaches $S$, shrink from $l$ to find the tightest window ending at $r$.

Because all entries are positive, the window sum is monotone in width, so once it drops below $S$ no further shrinking helps — the while exits and $r$ moves on.

Worked: longest substring without repeats. For Longest Substring Without Repeating Characters, the window must contain no duplicate character. We keep a map last[c] of the most recent index of each character. Expand $r$; if $a[r]$ was last seen at a position $\ge l$, that occurrence is inside the window, so we jump $l$ to one past it. The window $[l,r]$ is always duplicate-free, and we track its maximum length.

Each character is visited once by $r$, and $l$ only moves forward, so this is $O(n)$ time and $O(\sigma )$ space for an alphabet of size $\sigma$.

Prefix sums

The sliding window assumed we could update a sum incrementally. Prefix sums generalize this to answer any range-sum query in $O(1)$ after a linear precompute. Define

so $P$ has length $n+1$ and is built in one pass: $P[i]=P[i-1]+a[i-1]$. Then the sum of any subarray telescopes:

The highlighted entries are $P[2]=4$ and $P[5]=14$; their difference $10$ is exactly $a[2]+a[3]+a[4]=4+1+5$. One subtraction, no rescanning.

Counting subarrays with sum $=k$. Prefix sums turn a $\Theta (n^2)$ subarray scan into $O(n)$ for Subarray Sum Equals K. A subarray $(i,j)$ has sum $k$ iff $P[j+1]-P[i]=k$, i.e. $P[i]=P[j+1]-k$. So as we sweep a running prefix $P[j+1]$ left to right, the number of valid left endpoints is the number of earlier prefixes equal to $P[j+1]-k$. Keep a hash map of prefix-value frequencies seen so far:

Seeding freq with $\{0:1\}$ accounts for subarrays that start at index $0$ (those need $P[i]=0$). One pass, $O(n)$ time and space. Note this works for any integers, positive or negative, unlike the sliding window, which needed positivity for monotonicity.

Difference arrays, the dual. To apply many range updates "add $v$ to every $a[i\dots j]$" and only then read the array, invert the relationship. Keep a difference array $D$ and for each update do $D[i]+=v$ and $D[j+1]-=v$, two $O(1)$ touches. A single prefix-sum pass over $D$ at the end materializes the final array, since $a[i]=D[0]+\cdots +D[i]$. Thus $m$ range-adds cost $O(m+n)$ instead of $O(mn)$.

Prefix sums extend to two dimensions as well: precompute $P[i][j]={\sum }_{i^{\prime }<i,j^{\prime }<j}a[i^{\prime }][j^{\prime }]$, and any axis-aligned rectangle sum is recovered by inclusion–exclusion with four lookups in $O(1)$.

Takeaways

• These idioms all replace a $\Theta (n^2)$ pair-or-subarray scan with a single $O(n)$ pass by maintaining an invariant as indices advance and patching it in $O(1)$ per step.³
• Two pointers from opposite ends solve sorted-array pair problems (Two Sum II, Container With Most Water): the move that discards an index provably discards no solution, giving $O(n)$ time, $O(1)$ space.
• Fast/slow pointers (a trailing write behind a read) rewrite an array in place, dedup or partition, in $O(n)$ time and $O(1)$ extra space.
• A sliding window expands $r$ and shrinks $l$ to keep a property; since each index enters and leaves the window once, the nested loop is amortized $O(n)$.
• Prefix sums $P[i]={\sum }_{j<i}a[j]$ answer any range sum as $P[r+1]-P[l]$ in $O(1)$, and a hash map of prefix frequencies counts subarrays with sum $k$ in $O(n)$, even with negative numbers.
• The difference-array dual turns $m$ range-adds into $O(m+n)$, and prefix sums generalize to 2-D rectangle queries in $O(1)$.