The Pareto Dominance Invariant: Value vs. Expiration Time
Consider computing the maximum of every contiguous window of length $K$ across $A[0 \dots N-1]$. A balanced BST (std::multiset) or Binary Heap takes $O(N \log K)$ time because it retains every element in the window. Why is retaining all $K$ elements wasteful? Suppose index $i < R$ is currently inside the window, and the newly arriving element at index $R$ satisfies $A[i] \le A[R]$.
Compare $i$ and $R$ across two dimensions: (1) Value: $A[R] \ge A[i]$, and (2) Lifetime: $R > i$, so $R$ will remain inside all future sliding windows strictly longer than $i$ will! In optimization theory, $R$ Pareto-dominates $i$: $i$ can never be the maximum of the current window or any future window. Therefore, we can permanently discard $i$ from the back of our candidate list before pushing $R$!
At the end of step $R$ (for window $[R - K + 1, R]$), the indices $d_0, d_1, \dots, d_m$ stored in the deque from front to back simultaneously satisfy two strict invariants:
- Strictly Increasing Indices (Timestamps): $R - K + 1 \le d_0 < d_1 < \dots < d_m = R$.
- Strictly Decreasing Values: $A[d_0] > A[d_1] > \dots > A[d_m]$.
Consequently, $d_0 = \text{deque.front()}$ is guaranteed to be a valid in-window index holding the maximum value of $A[R - K + 1 \dots R]$ in $O(1)$ time! Each index $0 \dots N-1$ is pushed to the back once and popped from either the back (by dominance) or the front (by window expiration) at most once, proving $O(1)$ amortized work per step ($\le 2N$ deque operations total).
Sliding Window Extremum & Constrained DP Techniques Compared
| Method | Total Time (Length $N$) | Worst-Case Latency per Step | Auxiliary Space | Supports Dynamic Window Bounds $[L(R), R]$? |
|---|---|---|---|---|
| Naive Window Scan | $O(N K)$ | $O(K)$ | $O(1)$ | Yes |
| Balanced BST / Heap | $O(N \log K)$ | $O(\log K)$ | $O(K)$ | Yes |
| Monotonic Deque | $O(N)$ | $O(1)$ amortized ($O(K)$ worst step) | $O(K)$ | Yes! Any monotonic $[L(R), R]$ |
| Two-Stack Queue (Min-Stacks) | $O(N)$ | $O(1)$ amortized | $O(K)$ | Yes (works for ANY associative monoid!) |
Visualizing Back-Dominance Pruning & Front-Expiration
Monotonic Deque Optimization of DP & Negative-Weight Prefix Sums
while !dq.empty() && dq.front() < R - K + 1
dq.pop_front()"] B --> C["2. Prune Dominated Back:
while !dq.empty() && A[dq.back()] <= A[R]
dq.pop_back()"] C --> D["3. Insert & Query:
dq.push_back(R)
window_max = A[dq.front()]"]
std::deque by $4\times$When implementing a Monotonic Deque over an array of length $N$, since at most $N$ pushes ever occur across the entire algorithm, you don't even need a circular buffer! Allocating a flat std::vector<int> q(N) with two integer cursors int head = 0, tail = 0; implements pop_front() as ++head, pop_back() as --tail, and push_back(r) as q[tail++] = r. This reduces the entire monotonic deque to a single contiguous L1-cached array and two CPU registers.
Every index is pushed once and popped at most once. Inspect how maintaining a strict monotonic invariant resolves Next Greater/Smaller boundaries and sliding window extrema in O(N) time.
Invariant & State
Production Implementation: Sliding Window Maximum & Shortest Subarray with Sum $ge K$
#include <algorithm>
#include <cstdint>
#include <vector>
// O(N) Sliding Window Maximum using a register-indexed flat array deque
std::vector<int> sliding_window_maximum(const std::vector<int>& nums, std::size_t k) {
const std::size_t n = nums.size();
if (n == 0 || k == 0) return {};
std::vector<std::size_t> dq(n); // Flat array deque: at most N pushes total!
std::size_t head = 0, tail = 0;
std::vector<int> result;
result.reserve(n - k + 1);
for (std::size_t r = 0; r < n; ++r) {
// 1. Evict expired front index outside [r - k + 1 .. r]
if (head < tail && dq[head] + k <= r) {
++head;
}
// 2. Evict dominated back indices with value <= nums[r]
while (head < tail && nums[dq[tail - 1]] <= nums[r]) {
--tail;
}
dq[tail++] = r;
if (r + 1 >= k) {
result.push_back(nums[dq[head]]);
}
}
return result;
}
// LeetCode 862: Shortest Subarray with Sum >= K (handles negative numbers in O(N)!)
int shortest_subarray_sum_at_least_k(const std::vector<int>& nums, std::int64_t k) {
const std::size_t n = nums.size();
std::vector<std::int64_t> pref(n + 1, 0);
for (std::size_t i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + nums[i];
}
std::vector<std::size_t> dq(n + 1);
std::size_t head = 0, tail = 0;
std::size_t min_len = n + 1;
for (std::size_t r = 0; r <= n; ++r) {
// 1. Pop front while valid sum >= k is achieved; once L is paired with current R,
// no future R' > R can form a shorter subarray with L, so L is permanently retired!
while (head < tail && pref[r] - pref[dq[head]] >= k) {
min_len = std::min(min_len, r - dq[head]);
++head;
}
// 2. Maintain strictly increasing prefix sums in deque: if pref[back] >= pref[r],
// then r is both further right (shorter subarray) AND has a smaller prefix sum!
while (head < tail && pref[dq[tail - 1]] >= pref[r]) {
--tail;
}
dq[tail++] = r;
}
return (min_len <= n) ? static_cast<int>(min_len) : -1;
}A frequent bug is pushing values nums[r] into the deque instead of indices r. If you only store values, you cannot tell whether dq.front() has slid outside the left boundary $R - K + 1$ when duplicate values exist in the array! Always store array indices inside the monotonic deque (which gives you both the timestamp idx and the value nums[idx]). Also note the unsigned-safe expiration test: write dq[head] + k <= r instead of dq[head] <= r - k so r - k never underflows when r < k.