ii. Two Pointers and Sliding Window

Keep a window $[l,r]$ whose ends only move forward. Each pointer moves at most $n$ times, so the scan is $O(n)$ times the cost of updating the window.

The template

for (int l = 0, r = 0; r < n; r++) {
    add(a[r]);
    while (!valid()) remove(a[l++]);
    // [l, r] is the longest valid window ending at r
    best = max(best, r - l + 1);
    cnt += r - l + 1;                  // number of valid windows ending at r
}

• Shortest valid window: while (valid()) { best = min(best, r - l + 1); remove(a[l++]); }.
• Exactly $k$ = at most $k$ − at most $k-1$ (distinct values, odd numbers, sum with non-negative values).
• Requirement: validity is monotone. If $[l,r]$ is valid, every sub-window is valid (or every super-window, for the shortest-window form).

Proof: the two-pointer template is correct and $O(n)$

Correctness. By induction on $r$: suppose before processing $r$, $l$ is the smallest index making $[l,r-1]$ valid (or $l=r$ if no such window existed). After add(a[r]), $[l,r]$ may become invalid; the while shrinks $l$ one step at a time, and since validity of windows ending at $r$ is monotone in $l$ (sub-windows of an invalid-because-too-wide window stay invalid only until shrinking enough — formally, the monotonicity hypothesis says “valid at $l$ $⟹$ valid at every $l^{\prime }>l$ up to $r$”), the loop stops at exactly the smallest valid $l$, or at $l=r+1$ if even $[r,r]$ is invalid. So the invariant is maintained, and r-l+1 at each step is the longest valid window ending at $r$. Complexity. $l$ only increases and is bounded by $n$, so the total number of while-loop iterations across all $r$ is at most $n$; each add/remove call is charged once per unit of pointer movement, giving $O(n)$ total calls. $■$

Condition	Monotone?
sum $\le S$, values $\ge 0$	yes
sum $\le S$ with negatives	no: prefix sums + monotonic deque, or BIT
at most $k$ distinct	yes
$\max -\min \le D$	yes, with two monotonic deques
$\gcd \ge g$, $\mathrm{and}\ge x$, $\mathrm{or}\le x$	yes (the aggregate only moves one way as the window grows); use the two-stack queue for gcd
contains every required item	yes (shortest-window form)
sum exactly $S$	not in general: hash map of prefix sums

Window 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
$k$-th smallest	PBDS or two heaps
anything non-invertible (gcd, matrix product, …)	the two-stack queue (SWAG) below

Other two-pointer shapes

• Opposite ends of a sorted array: two-sum, counting pairs with $a_i+a_j\le X$, container with most water. Three-sum: fix one element, two pointers on the rest, $O(n^2)$. General $k$-sum: recurse by fixing one element and reducing to $(k-1)$-sum, down to two-pointers at $k=2$ — $k-2$ nested fixed loops plus one $O(n)$ two-pointer scan gives $O(n^{k-1})$, and this is believed optimal for $k\ge 3$ (3SUM-hardness, see fine-grained reductions).
• Two sorted sequences: merge, intersect, count pairs with $|a_i-b_j|\le d$.
• The pointer is a monotone function of $i$: whenever the optimal $j$ for $i$ is non-decreasing in $i$ (it often is for convex costs), a pointer replaces a binary search. This is the same monotonicity that powers DP optimisations.
• Fast and slow pointers: cycle detection in functional graphs (Floyd/Brent), middle of a list.

Monotonic deque: sliding window min/max

deque<int> dq;                                     // indices; values decreasing front to back
for (int i = 0; i < n; i++) {
    while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
    dq.push_back(i);
    if (dq.front() <= i - k) dq.pop_front();
    if (i >= k - 1) out.push_back(a[dq.front()]);  // max of a[i-k+1..i]
}

An element dominated by a newer, larger one can never be the maximum again, so popping it is safe. Each index is pushed and popped once, $O(n)$ total.

Proof: popping is safe and the deque is $O(n)$

Safety. If a[j] <= a[i] with $j<i$, then for any future window $W$ containing $j$: since $i>j$ and the window’s right edge only grows, once $W$‘s right edge reaches $i$, if $j$ is still in $W$ then $i$ is too (as $j<i\le$ right edge and the window is contiguous, provided $i$ hasn’t already fallen out the left — but $i$ entered after $j$ so it falls out no earlier). So every window containing $j$ from this point on also contains $i$, and $a[i]\ge a[j]$ means $i$ is at least as good a maximum candidate; $j$ can safely be discarded. Monotonicity is preserved: the deque is maintained decreasing front-to-back by construction (the while pops everything $\le a[i]$ before pushing $i$), so dq.front() is always the maximum of the current window. Complexity. Each index is pushed exactly once; it is popped at most once (from the back, when dominated, or from the front, when it falls outside the window), so the total work across all $n$ iterations is $O(n)$. $■$

Uses:

• DP over a window: $d{p}_i={\min }_{i-k\le j<i}d{p}_j+c_i$ (Monotone Queue Optimization); bounded knapsack in $O(nW)$ by running a window per residue class mod weight.
• Shortest subarray with sum $\ge K$, negatives allowed: a deque of prefix indices with increasing $p$; pop the front while $p_i-p_{\text{front}}\ge K$, recording the length.
• Max sum with length in $[A,B]$: a deque of the minimum $p_l$ over $l\in [r-B,r-A]$.
• 2D sliding window max ($k\times k$ windows): run the 1D deque along rows, then along columns of the result. $O(nm)$.

Two-stack queue (SWAG)

A queue built from two stacks supports any associative operation, even non-invertible ones (gcd, min, matrix product, function composition), in $O(1)$ amortized per push, pop and query. Each stack stores the running aggregate. The back stack aggregates bottom to top; the front stack is filled by moving everything over when it’s empty and aggregates in reverse.

template<class T, class Op> struct SWAG {      // queue with fold of all elements, op associative
    Op op; T id;
    vector<T> fv, fa, bv; T ba;                // front values/aggregates, back values/aggregate
    SWAG(Op o, T e) : op(o), id(e), ba(e) {}
    void push(T x) { bv.push_back(x); ba = op(ba, x); }
    void pop() {
        if (fv.empty()) {                      // move back stack to front
            while (!bv.empty()) { T x = bv.back(); bv.pop_back(); fv.push_back(x); fa.push_back(fa.empty() ? x : op(x, fa.back())); }
            ba = id;
        }
        fv.pop_back(); fa.pop_back();
    }
    T query() const { return op(fa.empty() ? id : fa.back(), ba); }   // fold front-to-back
};

This is what you use for “two pointers with gcd / with matrix composition”, and for “Mo’s algorithm needs removals but the aggregate can’t remove” when the queries form a sliding window.

Proof: the two-stack queue is correct and $O(1)$ amortized

Correctness. The queue’s elements, in FIFO order, are exactly fv reversed followed by bv (front-to-back: oldest-pushed-and-not-yet-popped first). fa.back() holds the fold of all of fv in queue order (built incrementally as op(x, fa.back()) when moving an element from bv to fv, which reverses bv’s stack order back into queue order), and ba holds the fold of bv in push order, which is already queue order since bv only ever receives pushes at the back. So query() folding fa.back() then ba gives the fold of the whole queue in order — correct even for non-commutative op, since both halves preserve queue order internally and are combined in the right order. Amortized cost. Each element is pushed to bv once ($O(1)$), later moved from bv to fv at most once (the move happens only when fv is empty, and moves every element of bv across in one pass), and popped from fv once. Charging the move’s cost to the elements moved, each element participates in at most one push, one move, and one pop over its lifetime, so total work over $n$ operations is $O(n)$, i.e. $O(1)$ amortized per operation. $■$

Min stack: store (value, min so far) per element, $O(1)$ per op since a stack’s minimum only ever depends on a prefix of it. Min queue: two min stacks (in receives pushes, out serves pops; when out empties, move everything from in across, reversing order; the queue’s minimum is the smaller of the two stacks’ minimums) — each element moves from in to out exactly once, so $O(1)$ amortized. For a sliding window specifically the monotonic deque above is simpler and has a better constant, but it needs to know which value is leaving (FIFO order only); the two-stack version works for any push/pop sequence.

Situation	Structure
sliding window over an array	monotonic deque
arbitrary push/pop, need the minimum	two-stack minimum queue
LIFO only	minimum stack
need arbitrary deletion	multiset, $O(\log n)$

The two-stack minimum queue is what makes Mo’s algorithm with rollback work for a non-invertible aggregate (min needs both add and remove; when remove is impossible, this stack-based structure with undo substitutes), and it’s the same trick behind simulating a full min-deque with two stacks.

When it fails

If the left end sometimes needs to move back, two pointers don’t apply. Alternatives:

• binary search on the window length, when validity is monotone in length;
• a segment tree or sparse table to query arbitrary windows;
• divide and conquer on the array: count windows that cross the midpoint, and solve each half recursively;
• Mo’s algorithm for offline arbitrary ranges.