---
title: Two Pointers & Sliding Windows
module: Sequences & Strings
moduleNumber: 5
lessonNumber: 1
order: 501
summary: |
  A family of array idioms that collapse an obvious $O(n^2)$ scan into a single
  $O(n)$ pass by maintaining an invariant as indices move. We meet two pointers
  (converging on a sorted array, and a fast/slow pair for in-place rewriting)
  and the sliding window (fixed and variable size, amortized $O(n)$). The
  companion lesson on prefix sums picks up where the window's positivity
  assumption fails.
topics: [Array Techniques]
sources:
  - book: Skiena
    ref: "§ — Sorting & array techniques"
  - book: Erickson
    ref: "Ch. — Arrays and Amortization"
  - book: CLRS
    ref: "Ch. 2 — Getting Started"
practice:
  - title: 'Two Sum II - Input Array Is Sorted'
    slug: two-sum-ii-input-array-is-sorted
    difficulty: Medium
  - title: 'Container With Most Water'
    slug: container-with-most-water
    difficulty: Medium
  - title: 'Longest Substring Without Repeating Characters'
    slug: longest-substring-without-repeating-characters
    difficulty: Medium
  - title: 'Minimum Size Subarray Sum'
    slug: minimum-size-subarray-sum
    difficulty: Medium
---

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)$.[^erickson-amortize] 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.[^clrs-invariant]

## Two pointers, opposite ends

The cleanest instance lives on a **sorted** array. Suppose $a[0\ldots 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 $\binom{n}{2}$ pairs. Instead, place one pointer at
each end, $l = 0$ and $r = n-1$, and let them converge:

> **Invariant.** No pair $(i, j)$ with $i < l$ or $j > r$ can be the answer.
> Equivalently, if a solution exists, it lies in the window $[l, r]$.

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

> **Lemma.** Each move preserves the invariant: the discarded index belongs to no
> solution, so removing it loses no answer.
>

> **Proof.** Suppose $s = a[l] + a[r] < T$. For any $j$ with $l < j \le r$ we have
> $a[j] \le a[r]$ (sortedness), hence $a[l] + a[j] \le s < T$. So $a[l]$ forms no
> valid pair within the window, and advancing $l$ discards only non-solutions.
> The case $s > T$ is symmetric. $\qed$

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 $\binom{n}{2}$ comparisons to establish
that certificate of absence; the invariant gives it in $n-1$.

$$
% caption: The exclusion invariant midway through a scan: every index left of $l$ was
%          proven too small to appear in any pair, every index right of $r$ too large.
%          If a pair summing to $T$ exists, both of its ends lie in $[l,r]$
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \fill[black] (-0.42,-0.42) rectangle (2.22,0.42);
  \fill[black] (6.78,-0.42) rectangle (8.52,0.42);
  \fill[acc!8] (2.28,-0.42) rectangle (6.72,0.42);
  \foreach \i in {0,...,9} {
    \node[draw=black, minimum size=8mm, inner sep=1pt] (c\i) at (\i*0.9,0) {};
    \node[font=\footnotesize, black] at (\i*0.9,0.62) {\i};
  }
  \draw[acc, very thick] (2.24,-0.5) rectangle (6.76,0.5);
  \node[font=\footnotesize, black] at (0.9,-0.8) {proven to\/o small};
  \node[font=\footnotesize, black] at (7.65,-0.8) {proven to\/o large};
  \node[acc] (ll) at (2.7,-1.55) {$l$};
  \draw[->, acc, thick] (ll.north) -- (2.7,-0.58);
  \node[acc] (rr) at (6.3,-1.55) {$r$};
  \draw[->, acc, thick] (rr.north) -- (6.3,-0.58);
  \node[font=\footnotesize, acc] at (4.5,-1.55) {any solution lies here};
\end{tikzpicture}
$$

Here is the full run on $a = \langle 1,3,4,6,8,11\rangle$ 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 \gets 4$.
2. $(0, 4)$: $s = 1 + 8 = 9 < 10$. Now $a[0] = 1$ falls short even with the
   largest remaining partner: $l \gets 1$.
3. $(1, 4)$: $s = 3 + 8 = 11 > 10$, so $r \gets 3$.
4. $(1, 3)$: $s = 3 + 6 = 9 < 10$, so $l \gets 2$.
5. $(2, 3)$: $s = 4 + 6 = 10 = T$. Done.

$$
% caption: Converging pointers on sorted $\langle 1,3,4,6,8,11\rangle$, target $T=10$.
%          Each step compares $s=a[l]+a[r]$ to $T$ and discards one end; the pair
%          $a[2]+a[3]=10$ is found in five steps
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\v in {0/1,1/3,2/4,3/6,4/8,5/11} {
    \node[draw, minimum size=8mm, inner sep=1pt] (a\i) at (\i*0.95,0) {$\v$};
    \node[font=\footnotesize] at (\i*0.95,0.62) {\i};
  }
  \draw[acc, very thick] (1.45,-0.5) rectangle (3.35,0.5);
  \node[font=\footnotesize, acc] at (2.4,-1.0) {a[2] + a[3] = 10 = T};
  \node[font=\footnotesize] at (-1.5,-1.7) {$l$, $r$:};
  \node[font=\footnotesize] at (-0.1,-1.7) {0, 5};
  \node[font=\footnotesize] at (1.1,-1.7) {0, 4};
  \node[font=\footnotesize] at (2.3,-1.7) {1, 4};
  \node[font=\footnotesize] at (3.5,-1.7) {1, 3};
  \node[font=\footnotesize, acc] at (4.7,-1.7) {2, 3};
  \node[font=\footnotesize] at (-1.5,-2.25) {$s$:};
  \node[font=\footnotesize] at (-0.1,-2.25) {12 $>$ 10};
  \node[font=\footnotesize] at (1.1,-2.25) {9 $<$ 10};
  \node[font=\footnotesize] at (2.3,-2.25) {11 $>$ 10};
  \node[font=\footnotesize] at (3.5,-2.25) {9 $<$ 10};
  \node[font=\footnotesize, acc] at (4.7,-2.25) {10};
  \node[font=\footnotesize] at (-1.5,-2.8) {move:};
  \node[font=\footnotesize, acc] at (-0.1,-2.8) {r-{}-};
  \node[font=\footnotesize, acc] at (1.1,-2.8) {l++};
  \node[font=\footnotesize, acc] at (2.3,-2.8) {r-{}-};
  \node[font=\footnotesize, acc] at (3.5,-2.8) {l++};
  \node[font=\footnotesize, acc] at (4.7,-2.8) {done};
\end{tikzpicture}
$$

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](/algorithms/sorting/heaps-and-heapsort) 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](/algorithms/data-structures/hash-tables)
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.

::impl{algo="two_sum_sorted"}

The same converging-pointers move solves **Container With Most Water**: with
heights $a[0\ldots 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.

> **Claim.** Advancing the shorter wall discards no better container, so the
> single pass that always moves the shorter wall finds the maximum area.

> **Proof.** Suppose $a[l] \le a[r]$, so $l$ is the binding (shorter) wall. Any
> container that keeps $l$ fixed and moves $r$ inward to some $r' < r$ has width
> $r' - l < r - l$ and height $\min(a[l], a[r']) \le a[l]$, so its area is at most
> $(r - l)\cdot a[l]$, the current one. Thus no container using $l$ can beat what
> we already have, and we lose nothing by discarding $l$; advancing it is the only
> move that can raise the binding height. The case $a[r] < a[l]$ is symmetric.
> $\qed$

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

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.

::impl{algo="container_with_most_water"}

$$
% caption: Container With Most Water on $a=\langle 3,7,2,5,8,4\rangle$: the area is
%          $(r{-}l)\cdot\min(a[l],a[r])$, bound by the shorter wall, here $a[l]{=}3$,
%          giving $5\cdot 3=15$. Moving the taller wall $r$ inward only loses width at
%          the same capped height, so we advance the shorter wall $l$ instead
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.6,-1.75) rectangle (7.6,4.4);
  % water first, walls on top, so every bar stays visible
  \fill[acc!15] (0,0) rectangle (6.5,1.35);
  \draw[acc, very thick] (0,0) rectangle (6.5,1.35);
  % heights a = [3,7,2,5,8,4], walls l=0 (h=3), r=5 (h=4)
  \foreach \i/\h in {1/7,2/2,3/5,4/8} {
    \draw[black, thick] (\i*1.3,0) -- (\i*1.3,\h*0.45);
  }
  \foreach \i in {0,...,5} {
    \node[font=\footnotesize, black] at (\i*1.3,-0.35) {\i};
  }
  % emphasize the two walls
  \draw[acc, very thick] (0,0) -- (0,1.35);
  \draw[acc, very thick] (6.5,0) -- (6.5,1.8);
  \node[acc, font=\footnotesize] at (0,-0.8) {$l$};
  \node[acc, font=\footnotesize] at (6.5,-0.8) {$r$};
  \node[acc, font=\footnotesize] at (3.25,-1.4) {area = 5 x 3 = 15};
  % binding height annotation
  \node[font=\footnotesize, align=center] at (2.4,3.5) {a[l] = 3 binds: advance l};
  \draw[->, black, thick] (1.0,3.2) to[bend right=14] (0.18,1.55);
\end{tikzpicture}
$$

## 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:

> **Invariant.** $a[0 \ldots w-1]$ holds the de-duplicated prefix of everything
> read so far, in order.

```algorithm
caption: $\textsc{Dedup}(a)$ — compact a sorted array in place, returning new length
$w \gets 1$
for $r \gets 1$ to $n-1$ do
  if $a[r] \ne a[w-1]$ then
    $a[w] \gets a[r]$
    $w \gets w + 1$
return $w$
```

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 $\langle 1,1,2,3,3\rangle$:

- $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] \gets 2$ and set $w = 2$. The
  array now reads $\langle 1,2,2,3,3\rangle$.
- $r = 3$: $a[3] = 3 \ne a[1] = 2$, so write $a[2] \gets 3$, $w = 3$.
- $r = 4$: $a[4] = 3 = a[2]$; skip. Return $w = 3$: the prefix
  $\langle 1,2,3\rangle$ 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
$\langle 1,2\rangle$ even though the cells to its right still hold stale values.

$$
% caption: Fast/slow dedup on input $\langle 1,1,2,3,3\rangle$, frozen just before the
%          $r{=}3$ step: the write at $r{=}2$ overwrote $a[1]$ with $2$, so
%          $a[0\mathinner{\ldotp\ldotp} w{-}1]$ holds the compacted prefix $\langle 1,2\rangle$
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\v in {0/1,1/2,2/2,3/3,4/3} {
    \node[draw, minimum size=8mm, inner sep=1pt] (a\i) at (\i*0.9,0) {$\v$};
    \node[font=\footnotesize] at (\i*0.9,0.62) {\i};
  }
  \draw[acc, very thick] (-0.45,-0.5) rectangle (1.35,0.5);
  \node[acc, font=\footnotesize] at (0.45,-0.95) {unique so far};
  \node[acc] (rr) at (2.7,-1.6) {$r$};
  \draw[->, acc, thick] (rr.north) -- (a3.south);
  \node[font=\footnotesize] (ww) at (1.8,-1.6) {$w$};
  \draw[->, thick] (ww.north) -- (a2.south);
  \node[font=\footnotesize, acc] at (2.25,-2.2) {a[3] $>$ a[1]: write, w++};
\end{tikzpicture}
$$

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.

::impl{algo="dedup_sorted,partition_in_place"}

## 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} \mathrel{+}= a[r+1] - a[l]$. On $a = \langle 2,3,1,2,4,3\rangle$
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.)

::impl{algo="fixed_window_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:

> **Lemma (Amortized bound).** Across the whole run, $l$ and $r$ each advance from $0$ to
> $n$ and never retreat. Every index is added to the window exactly once (when $r$
> passes it) and removed at most once (when $l$ passes it), so the total work of
> both pointers is $O(n)$, even though the inner `while` can run several times in
> one outer step.[^erickson-amortize]

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.[^erickson-amortize]

$$
% caption: A variable window slides across the array; $l$ and $r$ each move only
%          rightward, so the pass is amortized $O(n)$
\begin{tikzpicture}[
  cell/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (c0) at (0,0) {$2$};
  \node[cell] (c1) at (0.8,0) {$3$};
  \node[cell] (c2) at (1.6,0) {$1$};
  \node[cell] (c3) at (2.4,0) {$2$};
  \node[cell] (c4) at (3.2,0) {$4$};
  \node[cell] (c5) at (4.0,0) {$3$};
  \node[cell] (c6) at (4.8,0) {$1$};
  \node[cell] (c7) at (5.6,0) {$2$};
  % highlight window over c2..c4
  \draw[acc, very thick]
    (1.2,-0.55) rectangle (3.6,0.55);
  % l pointer under left edge of window
  \node[acc, font=\small] (ll) at (1.6,-1.25) {$l$};
  \draw[->, acc, thick] (ll.north) -- (1.6,-0.6);
  \draw[->, acc, thick] (2.0,-1.25) -- (2.85,-1.25);
  % r pointer under right edge of window
  \node[acc, font=\small] (rr) at (3.2,-1.25) {$r$};
  \draw[->, acc, thick] (rr.north) -- (3.2,-0.6);
  \draw[->, acc, thick] (3.6,-1.25) -- (4.45,-1.25);
\end{tikzpicture}
$$

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

```algorithm
caption: $\textsc{MinSubarray}(a, S)$ — shortest window with sum $\ge S$, in $O(n)$
$l \gets 0,\ \ \text{sum} \gets 0,\ \ \text{best} \gets \infty$
for $r \gets 0$ to $n-1$ do
  $\text{sum} \gets \text{sum} + a[r]$
  while $\text{sum} \ge S$ do
    $\text{best} \gets \min(\text{best},\ r - l + 1)$
    $\text{sum} \gets \text{sum} - a[l]$
    $l \gets l + 1$
return $(\text{best} = \infty)\ ?\ 0 : \text{best}$
```

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 = \langle 2,3,1,2,4,3\rangle$ 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 $\langle 4,3\rangle$. 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.

$$
% caption: $\textsc{MinSubarray}$ on $\langle 2,3,1,2,4,3\rangle$ with $S=7$: each row
%          shows a window state, with the window sum and the action taken at the right.
%          Both pointers only ever move right; the best window $\langle 4,3\rangle$ has length 2
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {0,...,5} {
    \node[black] at (\i*0.8,0.58) {\i};
  }
  \foreach \y in {0,-1.3,-2.6,-3.9,-5.2} {
    \foreach \i/\v in {0/2,1/3,2/1,3/2,4/4,5/3} {
      \node[draw=black, minimum size=7mm, inner sep=1pt] at (\i*0.8,\y) {$\v$};
    }
  }
  \draw[acc, very thick] (-0.4,-0.44) rectangle (2.8,0.44);
  \draw[acc, very thick] (0.4,-1.74) rectangle (2.8,-0.86);
  \draw[acc, very thick] (1.2,-3.04) rectangle (3.6,-2.16);
  \draw[acc, very thick] (2.0,-4.34) rectangle (4.4,-3.46);
  \draw[acc, very thick] (2.8,-5.64) rectangle (4.4,-4.76);
  \node[anchor=west] at (4.9,0) {sum 8: record len 4, shrink};
  \node[anchor=west] at (4.9,-1.3) {sum 6: grow};
  \node[anchor=west] at (4.9,-2.6) {sum 7: record len 3, shrink};
  \node[anchor=west] at (4.9,-3.9) {sum 9: record len 3, shrink};
  \node[anchor=west, acc] at (4.9,-5.2) {sum 7: len 2, best};
\end{tikzpicture}
$$

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 = \langle 1, -1, 5\rangle$ 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 $\langle 5\rangle$ 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](/algorithms/sequences/monotonic-stacks))
instead of a window.

::impl{algo="min_size_subarray_sum"}

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

```algorithm
caption: $\textsc{LongestUnique}(a)$ — longest duplicate-free window, in $O(n)$
$l \gets 0,\ \ \text{best} \gets 0,\ \ \text{last} \gets \{\}$
for $r \gets 0$ to $n-1$ do
  if $a[r] \in \text{last}$ and $\text{last}[a[r]] \ge l$ then
    $l \gets \text{last}[a[r]] + 1$
  $\text{last}[a[r]] \gets r$
  $\text{best} \gets \max(\text{best},\ r - l + 1)$
return $\text{best}$
```

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 \gets 1$; the window
  $[1, 3]$ is `bca`.
- $r = 4$: `b` last at $1 \ge 1$, so $l \gets 2$: `cab`. $r = 5$: `c` last at
  $2$, so $l \gets 3$: `abc`.
- $r = 6$: `b` last at $4 \ge 3$, so $l$ _jumps_ to $5$: `cb`. $r = 7$: `b`
  last at $6$, so $l \gets 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.

$$
% caption: $\textsc{LongestUnique}$ on \texttt{abcabcbb}, at the moment $r$ reaches the
%          second \texttt{a} (index 3): the map says \texttt{a} was last seen at index
%          $0 \ge l$, so $l$ jumps to $1$ and the window $[1,3]$ is duplicate-free again
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \fill[acc!15] (-0.38,-0.38) rectangle (0.38,0.38);
  \fill[acc!15] (2.32,-0.38) rectangle (3.08,0.38);
  \foreach \i/\v in {0/a,1/b,2/c,3/a,4/b,5/c,6/b,7/b} {
    \node[draw, minimum size=8mm, inner sep=1pt] (c\i) at (\i*0.9,0) {\texttt{\v}};
    \node[font=\footnotesize, black] at (\i*0.9,0.62) {\i};
  }
  \draw[acc, very thick] (0.45,-0.5) rectangle (3.15,0.5);
  \node[acc] (rr) at (2.7,-1.25) {$r$};
  \draw[->, acc, thick] (rr.north) -- (c3.south);
  \node (ll) at (0.9,-1.25) {$l$};
  \draw[->, thick] (ll.north) -- (c1.south);
  \draw[->, black, thick, dashed] (0,-0.75) to[bend right=28] (0.75,-1.02);
  \node[font=\footnotesize, black, anchor=west] at (3.6,-1.25)
    {duplicate \texttt{a}: l jumps to 1};
\end{tikzpicture}
$$

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}[\texttt{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.

::impl{algo="longest_unique_substring"}

## 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](/algorithms/sequences/monotonic-stacks).
- **Contiguous subarrays with negative entries**, or exact-sum counting, break
  the window's monotonicity outright. Prefix sums handle these: see the
  [companion lesson](/algorithms/sequences/prefix-sums).

## 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.[^skiena-array]
- **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](/algorithms/sequences/prefix-sums),
which restores range-sum queries and subarray counting when the window's
positivity assumption no longer holds.

[^erickson-amortize]: **Erickson**, Ch. — Arrays and Amortization: the amortized argument that a two-pointer window, though nested, does $O(n)$ total work because each index is enqueued and dequeued once.
[^clrs-invariant]: **CLRS**, Ch. 2 — Getting Started (§2.1): the loop-invariant method (initialization, maintenance, termination) used here to prove each pointer scheme correct.
[^skiena-array]: **Skiena**, § — Sorting & array techniques: two-pointer and windowing idioms on sorted arrays as the linear-time alternative to a quadratic scan.