Two Pointers & Sliding Windows

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) 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 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 invariant has a picture worth keeping in mind. At every moment the array is split into three zones: a left zone of indices already discarded because each was proven too small to pair with anything that remained, a right zone discarded as too large, and the live window $[l,r]$ in between. The lemma says every discard is safe, so by induction the window always contains both ends of every surviving candidate pair. When the pointers meet, the window holds fewer than two indices, and we may conclude that no solution exists at all — not merely that we failed to find one. The brute-force scan needs $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ comparisons to establish that certificate of absence; the invariant gives it in $n-1$.

Here is the full run on $a=⟨1,3,4,6,8,11⟩$ with target $T=10$:

1. $(l,r)=(0,5)$: $s=1+11=12>10$. Even the smallest available partner overshoots with $a[5]=11$, so index $5$ joins no pair: $r\leftarrow 4$.
2. $(0,4)$: $s=1+8=9<10$. Now $a[0]=1$ falls short even with the largest remaining partner: $l\leftarrow 1$.
3. $(1,4)$: $s=3+8=11>10$, so $r\leftarrow 3$.
4. $(1,3)$: $s=3+6=9<10$, so $l\leftarrow 2$.
5. $(2,3)$: $s=4+6=10=T$. Done.

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 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 comparison with the hash-table solution is worth making precise. On an unsorted array, one pass with a map answers Two Sum in $O(n)$ expected time: for each $a[j]$, look up $T-a[j]$ among the elements already inserted. That beats sort-then-scan's $O(n\log n)$, but it spends $O(n)$ extra space and gives expected rather than worst-case time. When the input arrives sorted, the pointers win outright: $O(n)$ worst case, $O(1)$ space, no hashing. One caveat if you sort yourself: sorting scrambles the original positions, so a problem that wants indices back forces you to sort (value, index) pairs first.

Two edge cases matter. The condition is $l<r$, strict, because an element cannot pair with itself; when the pointers meet, the invariant says the remaining window holds no pair, so report failure. And each miss must move exactly one pointer, the one the proof licenses. Moving $l$ when $s>T$ (or both pointers at once) discards indices the invariant has said nothing about, and solutions can be lost. Duplicates need no special handling for existence; to enumerate all distinct pairs, step past runs of equal values after each hit.

from typing import Optional, Sequence

def two_sum_sorted(values: Sequence[int], target: int) -> Optional[tuple[int, int]]:
  """
    Indices `(left, right)` with `left < right` and\n
    `values[left] + values[right] == target`, or None if no such pair\n
    exists. `values` must be sorted ascending.\n
  """
  left: int = 0
  right: int = len(values) - 1

  while left < right:
    current_sum: int = values[left] + values[right]
    if current_sum == target:
      return (left, right)

    # too small: raise the floor; too big: lower the ceiling.
    if current_sum < target:
      left += 1
    else:
      right -= 1

  return None

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.

One pass, $O(n)$. Here is the full run on $a=⟨3,7,2,5,8,4⟩$:

1. $(l,r)=(0,5)$: width $5$, height $\min (3,4)=3$, area $15$. $a[0]<a[5]$, so advance $l$.
2. $(1,5)$: width $4$, height $\min (7,4)=4$, area $16$. $a[5]<a[1]$, so retreat $r$.
3. $(1,4)$: width $3$, height $\min (7,8)=7$, area $21$. Advance $l$.
4. $(2,4)$: width $2$, height $\min (2,8)=2$, area $4$. Advance $l$.
5. $(3,4)$: width $1$, height $\min (5,8)=5$, area $5$. Advance $l$; the pointers meet. Maximum: $21$, between walls $1$ and $4$.

The candidate areas do not climb monotonically — step 4 drops to $4$ after the maximum has already been seen. The scan promises only that the true optimum is among the $n-1$ candidates it evaluates, which is what the claim guarantees: no discarded wall could have anchored anything better. When $a[l]=a[r]$, both proofs apply and either move is safe; advancing $l$ by convention keeps the code branch-free.

from typing import Sequence

def max_water_area(heights: Sequence[int]) -> int:
  """
    The maximum area of water any two walls in `heights` can hold.\n
    Returns 0 for fewer than two walls.\n
  """
  left: int = 0
  right: int = len(heights) - 1
  best_area: int = 0

  while left < right:
    # the binding wall is the shorter one; width shrinks as the ends close.
    width: int = right - left
    binding_height: int = min(heights[left], heights[right])
    best_area = max(best_area, width * binding_height)

    # advance the shorter wall — the only move that can raise the height.
    if heights[left] <= heights[right]:
      left += 1
    else:
      right -= 1

  return best_area

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. Trace it on $⟨1,1,2,3,3⟩$:

• $w=1$. At $r=1$: $a[1]=1=a[0]$, a duplicate; skip.
• $r=2$: $a[2]=2\ne a[0]=1$, so write $a[1]\leftarrow 2$ and set $w=2$. The array now reads $⟨1,2,2,3,3⟩$.
• $r=3$: $a[3]=3\ne a[1]=2$, so write $a[2]\leftarrow 3$, $w=3$.
• $r=4$: $a[4]=3=a[2]$; skip. Return $w=3$: the prefix $⟨1,2,3⟩$ is the answer, and everything past it is garbage the caller ignores.

The figure below freezes the run just before the $r=3$ step: the earlier write already replaced $a[1]$ with $2$, so the kept prefix reads $⟨1,2⟩$ even though the cells to its right still hold stale values.

Two details deserve care. The pseudocode assumes $n\ge 1$ (it initializes $w=1$, silently keeping $a[0]$); guard the empty array separately. And the filter is stable: kept elements retain their relative order, because the write pointer copies them in read order. The same skeleton solves remove element (keep everything not equal to a given $v$) and move zeroes (keep the nonzeros, then zero-fill from $w$ to the end) with a one-line change to the keep test. The trailing-write pattern also underlies in-place partition (the core of quicksort and quickselect), where a write pointer marks the boundary between elements already placed below the pivot and the rest; that variant swaps rather than copies, and gives up stability in exchange.

from typing import MutableSequence

def dedup_sorted(values: MutableSequence[int]) -> int:
  """
    Compact the sorted array `values` in place, overwriting its front with\n
    the distinct elements in order. Returns the count of distinct elements;\n
    `values[:count]` is the de-duplicated array.\n
  """
  if len(values) == 0:
    return 0

  # keep only elements that differ from the last one written.
  write: int = 1
  for read in range(1, len(values)):
    if values[read] != values[write - 1]:
      values[write] = values[read]
      write += 1
  return write

from typing import MutableSequence

def partition_in_place(
  values: MutableSequence[int], low: int, high: int
) -> int:
  """
    Partition `values[low .. high]` around the pivot `values[high]`.\n
    Rearranges the slice so everything left of the returned boundary is\n
    `<= pivot` and everything right is `> pivot`, and returns the final\n
    index of the pivot.\n
  """
  pivot: int = values[high]
  boundary: int = low

  # swap each element below the pivot down to the boundary.
  for read in range(low, high):
    if values[read] <= pivot:
      values[boundary], values[read] = values[read], values[boundary]
      boundary += 1

  # drop the pivot into its sorted position.
  values[boundary], values[high] = values[high], values[boundary]
  return boundary

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]$. On $a=⟨2,3,1,2,4,3⟩$ with $k=3$: the first window sums to $2+3+1=6$; sliding to $[1,3]$ gives $6+a[3]-a[0]=6+2-2=6$; then $[2,4]$ gives $6+4-3=7$; then $[3,5]$ gives $7+3-1=9$. Recomputing each window from scratch costs $(n-k+1)\cdot k$ additions; the incremental version pays $k$ for the first window and two operations per slide, $k+2(n-k)=O(n)$. (For floating-point data the running sum accumulates rounding error over many slides; recompute it from scratch periodically if that matters.)

from typing import Sequence

def fixed_window_sums(values: Sequence[int], width: int) -> list[int]:
  """
    The sum of every contiguous window of size `width` in `values`, in left\n
    to right order. Returns an empty list when `width` is non-positive or\n
    exceeds the length.\n
  """
  count: int = len(values)
  if width <= 0 or width > count:
    return []

  window_sum: int = sum(values[:width])
  sums: list[int] = [window_sum]

  # slide one step at a time: the new element enters, the oldest one leaves.
  for right in range(width, count):
    window_sum += values[right] - values[right - width]
    sums.append(window_sum)
  return sums

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:

The accounting behind the lemma is worth spelling out, because the same argument recurs across this module. Count pointer increments instead of loop iterations. The outer loop increments $r$ exactly $n$ times. Every pass through the inner while increments $l$; since $l$ never decreases and never exceeds $n$, the inner loop runs at most $n$ times summed over the entire outer loop, no matter how unevenly those shrinks cluster. One outer step may trigger five shrinks and the next ten steps none; the total is still bounded by $2n$ pointer moves, each with $O(1)$ bookkeeping attached. Equivalently, charge each element two coins: one spent when $r$ brings it into the window, one when $l$ evicts it. $2n$ coins pay for everything.¹

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.

Trace it on $a=⟨2,3,1,2,4,3⟩$ with $S=7$, watching the running sum:

• $r=0,1,2$: sums $2$, $5$, $6$ — all below $7$, the window just grows to $[0,2]$.
• $r=3$: sum $8\ge 7$. Record length $4$. Shrink: drop $a[0]=2$, sum $6$, $l=1$; below $7$, stop.
• $r=4$: sum $6+4=10\ge 7$. Record length $4$ (no improvement). Shrink: drop $a[1]=3$, sum $7$, $l=2$; still $\ge 7$, record length $3$. Shrink again: drop $a[2]=1$, sum $6$, $l=3$; stop.
• $r=5$: sum $6+3=9\ge 7$. Record length $3$ (tie). Shrink: drop $a[3]=2$, sum $7$, $l=4$; record length $2$. Shrink: drop $a[4]=4$, sum $3$, $l=5$; stop.

The answer is $2$, the window $⟨4,3⟩$. Every recorded window is the tightest one ending at its $r$, and the true optimum ends somewhere, so the minimum over all recordings is correct.

Edge cases: if no window ever reaches $S$, $\text{best}$ stays $\infty$ and we return $0$ by convention. If some single element $a[i]\ge S$, the shrink loop tightens the window to length $1$ the moment $r$ passes it, so the algorithm needs no special case for it.

The positivity assumption is essential. Take $a=⟨1,-1,5⟩$ and $S=5$: the scan reaches $r=2$ with sum $5$, records length $3$, shrinks once to sum $4<5$, and stops — final answer $3$. But $⟨5⟩$ alone is a valid window of length $1$. The shrink loop quit early because dropping $-1$ would have raised the sum back to $5$, and the once the sum dips below $S$, shrinking further never helps claim is false with negative entries. With mixed signs, use prefix sums plus a monotonic structure (a cousin of the monotonic stack) instead of a window.

from typing import Sequence

def min_size_subarray_sum(values: Sequence[int], target: int) -> int:
  """
    The length of the shortest contiguous subarray of `values` whose sum is\n
    at least `target`, or 0 if no such subarray exists. Assumes\n
    non-negative entries.\n
  """
  left: int = 0
  window_sum: int = 0
  best_length: int = len(values) + 1

  for right in range(len(values)):
    window_sum += values[right]

    # shrink from the left while the window still meets the target.
    while window_sum >= target:
      best_length = min(best_length, right - left + 1)
      window_sum -= values[left]
      left += 1

  return 0 if best_length == len(values) + 1 else best_length

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$.

On the string abcabcbb:

• $r=0,1,2$: a, b, c are all new; the window is $[0,2]$, $\text{best}=3$.
• $r=3$: a was last seen at index $0\ge l=0$, so $l\leftarrow 1$; the window $[1,3]$ is bca.
• $r=4$: b last at $1\ge 1$, so $l\leftarrow 2$: cab. $r=5$: c last at $2$, so $l\leftarrow 3$: abc.
• $r=6$: b last at $4\ge 3$, so $l$ jumps to $5$: cb. $r=7$: b last at $6$, so $l\leftarrow 7$: b.

$\text{best}$ never improves past $3$ (abc), and the jump at $r=6$ shows why the map beats shrinking one step at a time: $l$ moves straight past every index that cannot start a duplicate-free window.

The guard $\text{last}[a[r]]\ge l$ is the step most often botched. The map is never cleaned, so it accumulates stale entries for characters that have long since left the window, and acting on one moves $l$ backward. On abba: at $r=2$ the second b sends $l$ to $2$; at $r=3$, a has $\text{last}[\text{a}]=0<l$ — that occurrence sits outside the window and is no conflict. With the guard, the window $[2,3]$ = ba is correct. Without it, $l$ would retreat to $1$ and window $[1,3]$ = bba contains a duplicate, breaking the invariant and inflating the answer.

An equivalent formulation keeps a count map and shrinks one step at a time (while the entering character's count exceeds $1$, decrement the count of $a[l]$ and advance $l$). It runs in the same amortized $O(n)$ and generalizes more smoothly to constraints like at most $k$ distinct characters, where there is no single index to jump to.

def longest_unique_substring(text: str) -> int:
  """
    The length of the longest substring of `text` containing no repeated\n
    character.\n
  """
  last_seen: dict[str, int] = {}
  left: int = 0
  best_length: int = 0

  for right, character in enumerate(text):
    # if this character repeats inside the window, drop the left edge past it.
    previous: int = last_seen.get(character, -1)
    if previous >= left:
      left = previous + 1

    # record the latest position and stretch the best length to here.
    last_seen[character] = right
    best_length = max(best_length, right - left + 1)

  return best_length

Choosing the tool

The techniques overlap enough that recognizing which one fits is most of the work. A checklist for the pointer-and-window family:

• Sorted input, question about a pair (sum, difference, closest to a target): converging pointers from the ends. If the input is unsorted and order does not matter, sort first ($O(n\log n)$) or use a hash map ($O(n)$ time and space).
• One-pass, in-place rewrite (dedup, filter, compact): fast/slow pointers. Stable, $O(1)$ extra space.
• Optimize over contiguous subarrays, feasibility monotone in window width (all-positive sums, distinct-character counts): variable-size sliding window, amortized $O(n)$. The monotonicity is the license; check it before trusting the shrink loop.
• Sliding-window maximum or minimum fits none of the above (max is not invertible the way sums are) and needs the monotonic deque, covered in the next lesson.
• Contiguous subarrays with negative entries, or exact-sum counting, break the window's monotonicity outright. Prefix sums handle these: see the companion lesson.

Amortization, stream processing, and sweep lines

The amortized $O(n)$ argument for the variable window — each index enters and leaves once — is the same potential bookkeeping Tarjan formalized for data structures (Tarjan, Amortized Computational Complexity, SIAM J. Alg. Disc. Meth., 1985): assign each element a small constant of credit when it enters, spend it when it leaves, and the total spend bounds the whole run regardless of how unevenly the work clusters. The two-coin accounting in this lesson is that theorem in miniature.

Two-pointer and window scans also underpin stream processing. A fixed window of width $k$ over an unbounded stream — a moving average, a rate limiter counting events in the last $k$ seconds — reduces to the incremental add-the- entrant, subtract-the-departer update, and it is how time-series databases and monitoring systems (Prometheus's range queries, for instance) compute windowed aggregates without rescanning history. The distinction the lesson draws between invertible aggregates (sum, count — a departing element can be subtracted) and non-invertible ones (max, min — a departing maximum cannot be subtracted back out) is the line between what a plain running total handles and what needs the monotonic deque of the next lesson; the same split reappears in database window functions, where SUM() OVER slides cheaply but MAX() OVER does not.

Finally, the converging-pointer move on a sorted array is the one-dimensional base case of a recurring geometric pattern: 3Sum and k-Sum fix outer indices and run the two-pointer scan inside, and the same advance the provably useless end logic drives sweep-line algorithms in computational geometry (Preparata & Shamos, Computational Geometry, 1985), where a pointer sweeps a sorted event list and never backtracks.

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)$.
• The window needs its feasibility monotone in width — positivity for sums, a duplicate test for distinct characters. When negative entries break that monotonicity, the tool changes.

This continues in Prefix Sums & Difference Arrays, which restores range-sum queries and subarray counting when the window's positivity assumption no longer holds.