Two Pointers and Sliding Window

Maintain a window $[l,r]$ over an array, moving both ends monotonically. Each pointer advances at most $n$ times, so the whole scan is $O(n)$.

The sliding window template

int l = 0;
for (int r = 0; r < n; r++) {
    add(a[r]);                                 // extend the window
    while (!valid()) { remove(a[l]); l++; }    // shrink until valid
    best = max(best, r - l + 1);               // window [l, r] is valid
}

The whole design is in add, remove, and valid(). The loop shape never changes.

The three shapes

1. Longest valid window

As above: extend right, shrink left while invalid, record the length.
“Longest substring with at most $k$ distinct characters.”

2. Shortest valid window

for (int r = 0; r < n; r++) {
    add(a[r]);
    while (valid()) { best = min(best, r - l + 1); remove(a[l]); l++; }
}

Shrink while valid, recording before each shrink.
“Shortest subarray with sum $\ge S$.“

3. Count valid windows

for (int r = 0; r < n; r++) {
    add(a[r]);
    while (!valid()) { remove(a[l]); l++; }
    count += r - l + 1;                        // all windows ending at r
}

“Number of subarrays with at most $k$ distinct values.”

Exactly $k$ = (at most $k$) − (at most $k-1$). This subtraction trick converts a hard constraint into two easy ones and is worth remembering.

The requirement: monotonicity

Two pointers works only when extending the window never makes an invalid window valid, and shrinking never makes a valid window invalid. Formally, validity must be monotone in the window.

Condition	Monotone?
Sum $\le S$, all values $\ge 0$	✔
Sum $\le S$ with negative values	✘ — use prefix sums + a deque or a segment tree
At most $k$ distinct values	✔
Maximum − minimum $\le D$	✔ (with two monotonic deques)
Product $\le P$, all values $\ge 1$	✔
GCD of the window $\ge g$	✔ (gcd only decreases as the window grows)
Contains all of a required multiset	✔
Sum is exactly $S$	✘ in general — use a hash map of prefix sums

Two pointers on two arrays

int i = 0, j = 0;
while (i < n && j < m) {
    if (a[i] < b[j]) i++;
    else if (a[i] > b[j]) j++;
    else { /* match */ i++; j++; }
}

Uses: merging sorted arrays, intersecting sorted sets, counting pairs with a bounded difference, and the merge step of merge sort.

Opposite-direction pointers

int l = 0, r = n - 1;
while (l < r) {
    if (a[l] + a[r] == target) { /* found */ break; }
    if (a[l] + a[r] < target) l++; else r--;
}

For a sorted array: two-sum, three-sum (fix one, two-pointer the rest), container-with-most-water, and the trapping rain water problem.

Maintaining window aggregates

Aggregate	Structure
Sum, count	a running variable
Distinct count	a frequency map plus a counter
Maximum / minimum	monotonic deque, $O(1)$ amortized
Both max and min	two deques
GCD	a sparse table, or a stack-based min-queue analogue
$k$-th smallest	PBDS or two heaps
Anything non-invertible	the two-stack queue trick

The two-stack queue is the general answer: any aggregate a stack can maintain in $O(1)$ can be maintained by a queue at $O(1)$ amortized, so no “removal” operation is ever needed.

When two pointers fails

If the window’s left end must sometimes move backwards, the technique does not apply. Alternatives:

• prefix sums + a hash map (for exact-sum problems),
• segment tree or sqrt decomposition over the range,
• Mo’s algorithm for offline arbitrary ranges,
• binary search on the window length when validity is monotone in length.

See also: Monotonic Queue · Prefix Sum · Mo’s Algorithm