Sliding Window: Fixed, Variable and Monotonic-Deque Templates

A sliding window is a pair of pointers that marks a contiguous range of an array or string. Instead of recomputing every range from scratch, you update the answer as the window’s right edge moves forward and its left edge catches up, so an O(n²) or O(n·k) scan becomes O(n). It is one of the most common patterns in Data Engineering interviews, partly because it is exactly how streaming systems compute rolling metrics.

Every code block is self-contained and ends with assert tests.

How a sliding window works

The window is nums[left : right + 1]. You keep some state about it (a sum, a set, a Counter, a deque) and update that state in O(1) when an element enters on the right or leaves on the left.

Two families:

Family	Window size	Loop shape
Fixed	Always k	Add nums[right]; once the size exceeds k, remove nums[right - k]
Variable	Grows and shrinks	Add nums[right]; while the window breaks (or satisfies) a condition, remove nums[left] and advance left

A variable window works only when the condition is monotonic: if a window is invalid, every larger window containing it is also invalid (or, for “shortest” problems, if a window is valid, every larger one is too). That is why it handles “at most k distinct characters” but not “subarray sum equals k” with negative numbers; that one needs prefix sums.

Recognising the pattern

• The problem asks about a contiguous subarray or substring.
• It asks for the longest, shortest, maximum sum or count of such ranges.
• It mentions a size k, “at most k”, “without repeating”, or “contains all of”.
• Values are non-negative, or the condition depends on counts rather than sums.
• In a DE framing: “rolling”, “moving average”, “in the last N minutes”, “per window”.

Core templates in Python

Fixed-size window

def max_average_subarray(nums, k):
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # one in, one out
        best = max(best, window)
    return best / k


assert max_average_subarray([1, 12, -5, -6, 50, 3], 4) == 12.75
assert max_average_subarray([5], 1) == 5.0

Running minimum: a window that only remembers the best so far

Best Time to Buy and Sell Stock is a degenerate window: the left edge jumps to any new lowest price.

def max_profit(prices):
    lowest = float("inf")
    best = 0
    for price in prices:
        lowest = min(lowest, price)          # best day to have bought so far
        best = max(best, price - lowest)     # sell today
    return best


assert max_profit([7, 1, 5, 3, 6, 4]) == 5
assert max_profit([7, 6, 4, 3, 1]) == 0
assert max_profit([]) == 0

Longest valid window: shrink while invalid

def length_of_longest_substring(s):
    last_seen = {}                 # char -> last index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1          # jump past the previous copy
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


def character_replacement(s, k):
    counts = {}
    left = 0
    max_freq = 0                   # highest count of one letter seen in any window so far
    best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        max_freq = max(max_freq, counts[ch])
        while (right - left + 1) - max_freq > k:   # too many letters to replace
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best


assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0
assert length_of_longest_substring("abba") == 2
assert character_replacement("ABAB", 2) == 4
assert character_replacement("AABABBA", 1) == 4

The last_seen[ch] >= left check matters: in "abba", the second a was last seen before the window, so it must not move left backwards. In character_replacement, max_freq is never decreased; that is safe because the answer can only grow when a window beats the best frequency seen so far.

Fixed window with matching counts

from collections import Counter


def check_inclusion(pattern, text):
    k = len(pattern)
    if k > len(text):
        return False
    need = Counter(pattern)
    window = Counter(text[:k])
    if window == need:
        return True
    for right in range(k, len(text)):
        window[text[right]] += 1
        out = text[right - k]
        window[out] -= 1
        if window[out] == 0:
            del window[out]                   # keep zero counts out so == works
        if window == need:
            return True
    return False


assert check_inclusion("ab", "eidbaooo") is True
assert check_inclusion("ab", "eidboaoo") is False
assert check_inclusion("abc", "ab") is False

Comparing two Counters costs O(alphabet size), which is O(1) for a fixed alphabet. A faster variant tracks how many characters currently have the right count.

Shortest valid window: shrink while valid

from collections import Counter


def min_window(s, t):
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(t)                 # characters of t still not covered
    left = 0
    best = (float("inf"), 0, 0)      # (length, start, end)
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1                # may go negative: surplus copies
        while missing == 0:          # window is valid: try to shrink it
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right + 1)
            need[s[left]] += 1
            if need[s[left]] > 0:    # we just dropped a needed character
                missing += 1
            left += 1
    return s[best[1]:best[2]] if best[0] != float("inf") else ""


assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a"
assert min_window("a", "aa") == ""

Monotonic deque: maximum of every window

Keep indices in a deque whose values are decreasing. The front is always the window’s maximum; anything smaller than a newcomer can never be a maximum again, so it is dropped from the back.

from collections import deque


def max_sliding_window(nums, k):
    dq = deque()                     # indices; nums[dq[0]] is the max
    out = []
    for right, value in enumerate(nums):
        while dq and nums[dq[-1]] <= value:
            dq.pop()                 # smaller values are now useless
        dq.append(right)
        if dq[0] <= right - k:
            dq.popleft()             # front index fell out of the window
        if right >= k - 1:
            out.append(nums[dq[0]])
    return out


assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([1], 1) == [1]
assert max_sliding_window([9, 8, 7, 6], 2) == [9, 8, 7]

Each index is pushed and popped at most once, so the whole scan is O(n), compared with O(n·k) for calling max() on every window.

Complexity

Template	Time	Extra space
Fixed window sum or average	O(n)	O(1)
Longest substring without repeats	O(n)	O(alphabet)
Character replacement	O(n)	O(alphabet)
Permutation in string	O(n · alphabet), O(n) for a fixed alphabet	O(alphabet)
Minimum window substring	O(len(s) + len(t))	O(alphabet)
Sliding window maximum	O(n)	O(k)

Each pointer only moves forward, so even with a while inside the for, the total number of steps is at most 2n.

Variations and common bugs

• Off-by-one window length: the size of nums[left..right] inclusive is right - left + 1.
• Updating the answer in the wrong place: for “longest”, update after the window is made valid; for “shortest”, update inside the shrinking loop while it is still valid.
• Moving left backwards when jumping with a last-seen map (the "abba" case).
• Stale zero counts in a Counter breaking equality checks; delete keys that reach zero, or compare only the needed keys.
• Using a window when negative numbers break monotonicity. Use prefix sums.
• Recomputing max() or sum() of the window each step, which silently makes it O(n·k).
• Variants: “at most k distinct” (shrink while distinct count exceeds k); “exactly k” = at most k minus at most k − 1; minimum-size subarray sum (shortest valid window with a sum).

Sliding windows in data-engineering work

Streaming systems are sliding windows at scale:

• Rolling metrics. A moving average of latency, a rolling sum of revenue, or “requests per user in the last 5 minutes” is the fixed-window template keyed by time instead of by count.
• Window types. Spark Structured Streaming and Flink offer tumbling windows (fixed, non-overlapping), sliding windows (fixed size, overlapping by a slide interval) and session windows (closed by a gap of inactivity). Late data handling (watermarks) decides when a window’s state can be dropped, just as left advancing lets you discard old elements.
• Rate limiting and anomaly detection. A deque of timestamps answers “how many events in the last N seconds” in amortised O(1) per event; a monotonic deque gives the rolling max for spike detection.
• SQL. AVG(x) OVER (ORDER BY ts ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) is a fixed sliding window; RANGE frames are time-based ones.

from collections import deque


class RollingCounter:
    """Count events in the last `span` seconds; timestamps arrive in order."""

    def __init__(self, span):
        self.span = span
        self.events = deque()
        self.total = 0

    def add(self, ts, amount=1):
        self.events.append((ts, amount))
        self.total += amount
        self._evict(ts)

    def _evict(self, now):
        while self.events and self.events[0][0] <= now - self.span:
            _, old = self.events.popleft()
            self.total -= old

    def value(self, now):
        self._evict(now)
        return self.total


rc = RollingCounter(span=60)
for ts, amount in [(0, 5), (10, 3), (59, 2), (61, 4)]:
    rc.add(ts, amount)
assert rc.value(61) == 9          # the event at t=0 left the window at t=60
assert rc.value(130) == 0
print(rc.value(61), rc.value(130))

9 0

In an interview, mention what happens with out-of-order events: this simple class assumes ordered timestamps. A streaming engine buffers by event time and uses a watermark to decide when a window is final.

Problems in this pattern

Recommended order, easy to hard:

1. Best Time to Buy and Sell Stock (Easy): track the lowest price so far and the best profit selling today.
2. Maximum Average Subarray I (Easy): fixed window of size k; add one element and remove one per step.
3. Longest Substring Without Repeating Characters (Medium): variable window with a last-seen index map.
4. Longest Repeating Character Replacement (Medium): window is valid while its length minus the top letter count is at most k.
5. Permutation in String (Medium): fixed window of the pattern’s length with matching character counts.
6. Minimum Window Substring (Hard): expand until all required characters are covered, then shrink while still covered.
7. Sliding Window Maximum (Hard): monotonic decreasing deque of indices; the front is the maximum.

Practice questions

Why is a sliding window with a while loop inside a for loop still O(n)?

Both left and right only move forward and each moves at most n times. The inner loop’s total iterations across the whole run are bounded by n, so the combined work is O(2n) = O(n).

When does the sliding window technique fail, and what do you use instead?

It fails when the validity condition is not monotonic, for example “subarray sums to k” with negative numbers: extending the window can make the sum smaller, so you cannot tell when to shrink. Use prefix sums with a hash map of earlier prefix counts.

How do you count subarrays with exactly k distinct values?

Count subarrays with at most k distinct values and subtract those with at most k − 1. Each “at most” count is a variable window: for each right, after shrinking until the window has at most k distinct values, add right - left + 1 (the number of valid windows ending at right).

Explain the monotonic deque in Sliding Window Maximum.

The deque holds indices whose values decrease from front to back. When a new value arrives, every smaller value at the back can never be a maximum again (the newcomer is larger and stays in the window longer), so pop them. Pop the front when its index leaves the window. The front is then always the maximum, and each index is pushed and popped once, giving O(n).

Design a “failed logins per user in the last 10 minutes” alert for a stream of events.

Keep a per-user deque of timestamps (or per-minute counts to bound memory). On each event, append it and evict timestamps older than 10 minutes, then alert if the length exceeds the threshold. Remove users whose deque becomes empty to bound memory. In a streaming engine, express it as a sliding event-time window grouped by user with a watermark to handle late events.

What is the difference between tumbling, sliding and session windows?

Tumbling windows are fixed-size and non-overlapping, so each event belongs to exactly one window (for example hourly totals). Sliding windows have a fixed size and a smaller slide interval, so they overlap and an event can belong to several windows (a 10-minute window every minute). Session windows have no fixed size; a window closes after a gap with no events for that key, which suits user sessions.

Key takeaways

• Sliding windows solve contiguous-range problems in O(n) by updating state as elements enter and leave.
• Use a fixed window for size-k problems, shrink-while-invalid for “longest”, and shrink-while-valid for “shortest”.
• The condition must be monotonic; with negative numbers and sums, switch to prefix sums.
• A monotonic deque gives the window maximum or minimum in amortised O(1).
• Streaming rolling metrics, rate limits and tumbling, sliding and session windows are the same pattern applied to time.