When Is a Sliding Window Mathematically Valid?
Given an array $A[0 \dots N-1]$ and a validity predicate $P(L, R) \in \{\text{true}, \text{false}\}$ defined on contiguous subarrays $A[L \dots R]$, a variable sliding window advances $R$ from $0$ to $N-1$ and increments $L$ while maintaining validity. For this algorithm to be correct without ever backtracking $L$, the predicate $P$ must be hereditary (monotonic under inclusion):
$$[L', R'] \subseteq [L, R] \text{ and } P(L, R) = \text{true} \implies P(L', R') = \text{true}$$
Equivalently, by contraposition: if $[L, R]$ violates the constraint ($P(L, R) = \text{false}$), then any super-interval $[L, R']$ with $R' > R$ also violates the constraint, and any sub-interval $[L', R]$ with $L' > L$ moves closer to satisfying it. Define $L^*(R)$ as the smallest index $L$ (for longest valid window) or largest index $L$ (for shortest valid window) paired with right endpoint $R$. Monotonicity guarantees:
$$R_1 < R_2 \implies L^*(R_1) \le L^*(R_2)$$
Because both $L$ and $R$ start at $0$, only increment, and never exceed $N$, the inner while loop executes at most $N$ times across the entire run of the outer loop, proving an exact bound of at most $2N$ pointer steps ($O(1)$ amortized work per element).
Suppose we want to count the number of subarrays with exactly $K$ distinct elements (or sum $= K$ over binary/non-negative arrays). A naive single sliding window fails because for a fixed $R$, there is not a single boundary $L$, but a whole contiguous range $[L_{\text{min}}, L_{\text{max}}]$ of valid left endpoints where the window has exactly $K$ distinct elements.
However, the predicate $P_K(L, R) \equiv (\text{distinct}(A[L \dots R]) \le K)$ is strictly monotonic! For each $R$, once we shrink $L$ until $\text{distinct}(A[L \dots R]) \le K$, every subarray starting at $i \in [L, R]$ and ending at $R$ is a subset of $[L, R]$ and therefore also has $\le K$ distinct elements—contributing exactly $(R - L + 1)$ valid subarrays ending at $R$. By set difference:
$$\text{countExactly}(K) = \text{countAtMost}(K) - \text{countAtMost}(K - 1)$$
Sliding Window Archetypes & Validity Conditions
| Window Archetype | Monotonicity Prerequisite | Inner Loop Condition | State Update at Step $R$ | Failure Case (When It Breaks) |
|---|---|---|---|---|
| Fixed Window of Size $K$ | Invertible or rolling aggregator | if (R >= K) remove(A[R - K]) |
ans = best(ans, state) |
Non-invertible state without monotonic deque |
| Longest Valid Window | Expanding $R$ can only break validity; shrinking $L$ restores it | while (!valid(L, R)) remove(A[L++]) |
ans = max(ans, R - L + 1) after loop |
Negative numbers in sum $\le K$ (shrinking $L$ can increase sum!) |
| Shortest Valid Window | Expanding $R$ achieves validity; shrinking $L$ tests minimality | while (valid(L, R)) { ans = min(..); remove(A[L++]); } |
Recorded inside inner while loop |
Negative numbers in sum $\ge K$ |
| Count Exactly $K$ | Metric $f(L, R)$ is non-decreasing with window length | Two calls: atMost(K) - atMost(K - 1) |
total += (R - L + 1) per $R$ |
Non-monotonic metric (e.g. arbitrary signed sums) |
Visualizing Monotonic Frontier $L^*(R)$ & The $\text{atMost}(K)$ Counting Wedge
Amortized Execution Flow of Variable Sliding Window
Insert A[R] into window state"] --> B{"Is window [L..R]
valid?"} B -- "No (Invalid)" --> C["Remove A[L] from state
L++ (Monotonic advance)"] C --> B B -- "Yes (Valid)" --> D["Update optimal answer
or add (R - L + 1) to count"]
std::unordered_map in Sliding WindowsInside a sliding window loop, every step increments freq[A[R]] and decrements freq[A[L]]. Using std::unordered_map<char, int> for ASCII/UTF-8 byte streams or bounded integer alphabets performs a hash computation, bucket pointer dereference, and linked-list node chase on every single character—turning a 1-cycle operation into a 40-cycle L1/L2 cache stall. Allocating a stack-resident flat array int32_t freq[256] = {0} occupies exactly 1 KB (16 cache lines), remains permanently pinned in L1d cache, and executes window expansions/contractions in ~1.2 CPU clock cycles per byte.
Trace variable-length sliding window [L..R] and Dutch National Flag 3-way partitioning. Both L and R advance monotonically, guaranteeing at most 2N pointer movements.
Invariant & State
Production Implementation: Count Subarrays with Exactly K Distinct Integers
#include <cstdint>
#include <vector>
// Prerequisite: 0 <= nums[i] <= max_val (or coordinate-compressed to [0, N))
std::int64_t subarrays_at_most_k_distinct(const std::vector<int>& nums, int k, int max_val) {
if (k <= 0) return 0;
std::vector<int> freq(static_cast<std::size_t>(max_val + 1), 0);
int distinct = 0;
std::size_t left = 0;
std::int64_t total_subarrays = 0;
for (std::size_t right = 0; right < nums.size(); ++right) {
if (freq[nums[right]]++ == 0) {
++distinct;
}
while (distinct > k) {
if (--freq[nums[left]] == 0) {
--distinct;
}
++left;
}
// Every subarray [i .. right] with left <= i <= right has <= k distinct elements
total_subarrays += static_cast<std::int64_t>(right - left + 1);
}
return total_subarrays;
}
std::int64_t subarrays_exactly_k_distinct(const std::vector<int>& nums, int k, int max_val) {
return subarrays_at_most_k_distinct(nums, k, max_val)
- subarrays_at_most_k_distinct(nums, k - 1, max_val);
}Never use a standard two-pointer sliding window to find the shortest or longest subarray with sum $\ge K$ or $\le K$ when the input array can contain negative numbers! With negative values, shrinking the window by advancing $L$ past a negative number $A[L] < 0$ increases the window sum, and advancing $R$ across a negative number decreases the window sum. Monotonicity is destroyed, and $L^*(R)$ is no longer non-decreasing. When negative numbers are present:
- For Subarray Sum Equals $K$: use Prefix Sums + Hash Map ($O(N)$ time, $O(N)$ space).
- For Shortest Subarray with Sum $\ge K$ (LeetCode 862): use Prefix Sums + a Monotonic Increasing Deque ($O(N)$ time, $O(N)$ space).