Sliding Window Mechanism: Neat Figures, Intuition, and Worked Patterns

The sliding window mechanism is an algorithmic technique that uses two pointers to maintain information about a contiguous “window” of data while scanning once. Instead of recomputing answers for every overlapping subarray/substrings with nested loops, we “slide” the window by expanding it (moving the right pointer) and contracting it (moving the left pointer), updating an aggregate state incrementally. This often reduces time complexity from $O(n^2)$ to $O(n)$ by avoiding redundant work on overlapping ranges. 2

Mermaid intuition of the two-pointer “window sliding” idea:

Key window concepts:

• two pointers approach (left/right)
• fixed-size window (size $k$)
• variable-size window (expand/contract)
• invariant (e.g., “window always satisfies constraint”)

1) Core Picture: What “Sliding” Means

Think of the input as a row of elements. The window is the current contiguous segment we are considering.

Let the window be $A[L..R]$ (inclusive). At each step:

• Move $R$ right to include a new element.
• If the condition becomes invalid, move $L$ right to exclude elements until the condition becomes valid again.
• Record the best answer based on the valid window.

A neat “moving window” figure:

This “expand until invalid, then shrink until valid” strategy is the most common form of the sliding window pattern. 2

2) Fixed-Size Sliding Window (Window size is constant)

When the problem specifies a window length $k$ (e.g., “maximum sum of any subarray of size $k$”), we use a fixed-size window:

• Start with the first $k$ elements.
• Slide by one: remove $A[i]$, add $A[i+k]$.
• Update the answer.

Classic example: maximum sum of a subarray of size $k$ is a textbook sliding window use-case.

Figure: Fixed window of length $k$

Why it works (time intuition)

Each step changes the window sum by only two operations: subtract one leaving element and add one entering element—so the total work is linear in the input size. 2

3) Variable-Size Sliding Window (Window size adapts to conditions)

If the window length is not fixed, we typically maintain a condition (an invariant) over the window while scanning:

• Expand by moving $R$ right.
• While the condition is violated, contract by moving $L$ right.
• When the condition is valid, the current window is a candidate for the result.

This is commonly used in problems like:

• longest substring with at most $K$ distinct characters
• minimum window / minimum size subarray with sum ≥ target
• longest subarray where some constraint about frequency or sum holds

Variable-size sliding window is commonly described as using start/end pointers and an aggregate that represents the current window state. 2

Figure: Variable window with “invalid → shrink”

4) Sliding Window as an “Efficiency Invariant”

The invariant (e.g., “window sum ≤ target” or “distinct characters ≤ $K$”) prevents the window from growing arbitrarily. The crucial efficiency idea is:

• Each index moves forward only (monotonic pointers).
• Each element enters the window once (when $R$ passes it).
• Each element leaves the window at most once (when $L$ passes it).

That “each element is added/removed at most once” argument is why sliding window solutions are often linear time, commonly stated as $O(n)$. 2