parikshan

Sliding Window

The core idea

A contiguous range [left, right] that walks down the array. As right advances, the window grows; as a property gets violated, left advances to restore it. Every element enters the window at most once and leaves at most once, so total work is O(n) even though the window changes shape constantly.

Two flavours:

  1. Fixed-size window: width is given. Slide it. Easy.
  2. Variable-size window: width adjusts to maintain an invariant ("at most k distinct", "sum ≤ target", "all of T are inside"). Harder; this is where the pattern earns its keep.

A monotonic deque generalises this further for "minimum / maximum in a window".

When to reach for it

Trigger phrases:

  • "longest / shortest substring with ..."
  • "subarray of size k that ..."
  • "smallest window containing ..."
  • "k distinct characters / elements"
  • "rolling average / median / max"

The signature is: the answer is a contiguous range, and the constraint depends on the elements inside the window, not on their positions globally.

How to approach

  1. Decide the window's invariant. Write it down before you write any code.
  2. Walk right from 0 to n-1, including arr[right] in the window.
  3. While the invariant is violated, advance left, removing arr[left-1] from the window.
  4. After the inner loop, record the answer (the current window length or its content).

The structure inside the window is almost always a hash map of frequencies. Keep two integers: distinct count and window length.

Real-world applications

  • Rate limiters: requests in the last 60 seconds. The window slides by time.
  • Anomaly detection: rolling z-score of latency over the last N samples.
  • Network throughput: bytes per second, sliding 1-second window.
  • Stock indicators: moving averages, Bollinger bands.
  • Streaming dedup: detecting duplicate events within a recent window.

In the AI-integrated workspace

Agents often write sliding-window code with nested while loops on the inside ("while invariant violated, do X") and forget that the outer loop is also a while. The bug is when the agent writes both as if, making the shrink happen only once per iteration even when shrinking twice is needed. Any sliding-window code review starts with: "Is the inner shrink a while, not an if?".

The second mistake: an agent computing the answer inside the shrink loop, which produces results for invalid windows. Check that the answer is recorded only after the invariant is restored.

The third mistake, specific to monotonic deques: forgetting to pop from the front when the index falls out of the window. Always ask: "What pops from the front?".

Problems in this cluster

Easy: maximum-average-subarray-i, best-time-to-buy-and-sell-stock. Medium: longest-substring-without-repeating, longest-repeating-character-replacement, permutation-in-string, minimum-size-subarray-sum. Hard: minimum-window-substring, sliding-window-maximum.

Start with maximum-average-subarray-i. It is the fixed-size warm-up that gets the rhythm of the pattern into your fingers.