The Sliding Window Technique

The sliding-window technique keeps a contiguous stretch of an array or string, a "window", and moves it along, updating the answer a little at each step rather than recomputing it over the whole window every time. That incremental update is the whole point: if adding a new element and removing an old one is cheap, the entire scan costs $O(n)$ instead of the $O(n \times k)$ or $O(n^2)$ you would pay by recomputing each window from scratch.

If this sounds familiar to a trader, it should: a rolling 20-day moving average of prices is a sliding window. Each day you add today's price and drop the price from 21 days ago, you never re-add the whole 20-day block. The same trick that computes rolling averages and rolling volatility on a price series is what makes these interview problems fast.

There are two flavours. A fixed-size window has a set width k and just marches right one step at a time. A variable-size window grows its right edge to include more, then shrinks its left edge whenever some condition is violated, this is the two-pointer pattern applied to a running constraint.

The fixed window: add one, drop one

For a window of width k, keep a running sum. When the window slides right by one, the new sum is the old sum plus the element that just entered on the right, minus the element that just left on the left:

$$\text{sum}_{\text{new}} = \text{sum}_{\text{old}} + a_{\text{enter}} - a_{\text{leave}} .$$

Here $a_{\text{enter}}$ is the value newly inside the window, $a_{\text{leave}}$ is the value that fell out the back, and each slide costs a single addition and subtraction, $O(1)$. Over the whole array that is $O(n)$ total.

Worked example: max sum of any window of size 3

Take a = [2, 1, 5, 1, 3, 2, 4, 1, 2] and k = 3.

• Seed the first window [2,1,5], sum $= 8$. Best so far: 8.
• Slide: drop 2, add 1 → [1,5,1], sum $8 - 2 + 1 = 7$.
• Slide: drop 1, add 3 → [5,1,3], sum $7 - 1 + 3 = 9$. New best: 9.
• Slide: drop 5, add 2 → [1,3,2], sum $9 - 5 + 2 = 6$.
• Continue: [3,2,4] = 9, [2,4,1] = 7, [4,1,2] = 7.

The maximum window sum is 9. Each slide was one add and one subtract, so the whole thing is $O(n)$, versus $O(n \times k)$ if you re-summed each window.

def max_window_sum(a, k):     # O(n) time, O(1) space
    s = sum(a[:k])
    best = s
    for i in range(k, len(a)):
        s += a[i] - a[i - k]  # add entering, drop leaving
        best = max(best, s)
    return best

The variable window: grow right, shrink left

When the window's size is what you are solving for, expand the right edge greedily and contract the left edge only when a rule breaks. Classic case: the longest substring with no repeated character. Keep a set of characters currently in the window; push the right edge outward, and whenever the incoming character is already in the set, pop from the left until it is gone.

def longest_unique(s):        # O(n) time, O(min(n, alphabet)) space
    seen = set()
    left = best = 0
    for right, c in enumerate(s):
        while c in seen:      # shrink until c is removable
            seen.remove(s[left])
            left += 1
        seen.add(c)
        best = max(best, right - left + 1)
    return best

On "abcabcbb" the window grows to "abc" (length 3), then each repeat forces the left edge forward, and 3 stays the answer. Every index enters and leaves the window at most once, so it is $O(n)$, not $O(n^2)$, even though there are two loops. That is the set doing the "have I seen this?" check in $O(1)$.

Where it breaks

• The statistic must be incrementally updatable. Sums, counts, and min/max-with-a-deque slide cheaply. A statistic you cannot cheaply "undo" when an element leaves, an exact median, say, needs a heavier structure (two heaps).
• Windows are contiguous. Sliding windows only handle consecutive elements. If the problem allows gaps, it is a different technique.
• Off-by-one on the width. The window [left, right] has size right - left + 1; forgetting the +1 is the most common bug.

In quant-dev interviews this pattern owns the "subarray/substring" family: maximum-sum window, longest-unique-substring, minimum-window-substring, and subarrays under a product or sum bound. On the desk it is the same math behind every rolling mean, rolling volatility, and moving-average signal computed over a price series.