Window Optimization

Window optimization means choosing data structures so each slide is cheap: deque for min/max, Counter for multiset, bitmask for small alphabets, or monotonic queue for constrained KPIs.

Why this shows up in the real world

High-frequency trading maintains rolling min/max quotes with deques. Network routers optimize per-flow byte counters in hardware windows.

Core idea (explained for students)

If naive validation is O(window size), replace with incremental structures. Example: sliding window maximum uses deque storing decreasing indices.

Try this in Python

from collections import deque


def sliding_max(nums: list[int], k: int) -> list[int]:
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        while dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

Common mistakes

• Using max(window) each time—O(k) per step.
• Deque invariants documented poorly—bugs creep in during shrink.

Key takeaways

• When sums aren’t enough, reach for deque / heap / tree map.
• Complexity budget: aim O(n) total scans.