Sliding WindowSliding windows

01Why it exists

Reach for it when you see:Contiguous subarrays or substrings, the last k items, the last t seconds, the longest or shortest interval satisfying a condition, streaming statistics, rate limiting, add one and remove one.

02The core idea

A sliding window is a special case of same-direction two pointers: the interval between l and r is the "window", and on top of it you maintain statistics that can be updated incrementally (a sum, a set of counts, a set of characters). Moving r one step right adds the new element to the statistic; moving l one step right subtracts the old one. Nothing is recomputed over the whole interval, each element goes in and out exactly once, and each of those is O(1), so the total is O(n). The extra space is whatever the statistic costs: O(1) for a sum, and at most O(k) for a set or counter, where k is the window length or the size of the alphabet.

A fixed-length window is the simplest form: the length is always k, r and l advance together on every step, and the statistic gains a[r] and loses a[l-1]. The average of the last k samples, the largest sum of length k, and fixed-length anagram matching are all this shape.

A variable-length window is driven by a validity condition: r extends by one each step, and if the window becomes invalid (a repeated character, a sum over the limit), l moves right until it is valid again. If the question asks for the shortest valid interval instead, flip it around: shrink as far as you can while the window is valid, updating the answer as you shrink. What makes this work is that validity is monotone in the interval, and the two kinds of question need that monotonicity in opposite directions. For the longest, you need "shrinking a valid interval keeps it valid" (dropping one end of a substring with no repeats still leaves no repeats). For the shortest, you need "growing a valid interval keeps it valid" (when every element is positive, an interval whose sum is ≥ target still sums to ≥ target once you add another one). When the condition involves a sum, a single negative number destroys that monotonicity: l can no longer move only right, and you need prefix sums or another approach instead. To count the subarrays with exactly k distinct values, the condition itself is not monotone, so split it into the count with at most k distinct minus the count with at most k−1, where each r contributes the r − l + 1 valid subarrays that end at it.

The choice of statistic decides the cost of each step. A sum takes one variable; "is there a repeat" takes a set or a counting array; "the maximum in the window" cannot be maintained with a single variable at all — once the maximum leaves you do not know what the next one is — so it needs a monotonic deque, which is amortised O(1). A rate limiter's window is bounded by time rather than by count, so it stores timestamps in a queue and pops the expired ones off the left end, but it is the same idea underneath.

03The algorithm

1. 1Confirm the problem is about a contiguous interval and that validity is monotone as the interval grows and shrinks (for the longest: shrinking keeps it valid; for the shortest: growing keeps it valid). Decide what statistic the window carries — it has to support O(1) insertion and removal.
2. 2l = 0 and the statistic empty. for r in range(n): add a[r] to the statistic.
3. 3while the window is invalid: remove a[l] from the statistic and do l += 1. This inner loop runs at most n times in total, not n times per step.
4. 4The window is valid now, so update the answer with r − l + 1 (for the longest). For the shortest, put that update inside the shrinking loop and change its condition to shrink while the window is valid.
5. 5For a fixed length, drop the validity test altogether: once r ≥ k, remove a[r − k] on every step, and the window is always exactly k long.

04Interactive demo

The longest substring without repeating characters. The blue cells are the current window, and below it is the set of characters inside the window. When r lands on a character already in the set (shown in amber), it is not added yet; l moves right until that character leaves, and only then does it go in. The green underline marks the best interval so far.

05Code

Four pieces: the longest substring without repeats as a variable window, the maximum average as a fixed window, the shortest qualifying interval as the other kind of variable window, and a rate limiter whose window is a queue. Notice that the longest and shortest variants update the answer in different places.

# Variable window: longest substring without repeating characters (LeetCode 3)
# r takes in one more character each step; while the window is invalid (a repeat), l shrinks right until it is valid
def length_of_longest_substring(s):
    seen = set()                           # characters in the window
    l = 0
    best = 0
    for r, c in enumerate(s):
        while c in seen:                   # the window is invalid
            seen.remove(s[l])
            l += 1
        seen.add(c)
        best = max(best, r - l + 1)
    return best


# Fixed window: maximum average over a subarray of length k (LeetCode 643), assuming 1 <= k <= len(nums)
# Each slide: add the new element, drop the old one, never recompute the whole window
def max_average(nums, k):
    total = sum(nums[:k])
    best = total
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]     # one in, one out
        best = max(best, total)
    return best / k


# Another shape of variable window: shortest subarray with sum >= target (LeetCode 209)
# The moment the condition holds, shrink as far as you can, updating the answer as you shrink
# Precondition: nums is all positive. With negatives, shrinking the left end need not lower the sum, so the window breaks down
def min_subarray_len(target, nums):
    l = 0
    total = 0
    best = float("inf")
    for r, x in enumerate(nums):
        total += x
        while total >= target:             # valid, try to shrink it further
            best = min(best, r - l + 1)
            total -= nums[l]
            l += 1
    return 0 if best == float("inf") else best


# Rate limiting: at most limit requests within the last window seconds
# The queue is the window; expired entries are dropped from the left
from collections import deque

class RateLimiter:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.q = deque()                   # request timestamps, increasing

    def allow(self, now):
        while self.q and self.q[0] <= now - self.window:
            self.q.popleft()               # the left end of the window has expired
        if len(self.q) < self.limit:
            self.q.append(now)
            return True
        return False


if __name__ == "__main__":
    print(length_of_longest_substring("abcadbcxab"))   # 5
    print(max_average([1, 12, -5, -6, 50, 3], 4))      # 12.75
    print(min_subarray_len(7, [2, 3, 1, 2, 4, 3]))     # 2
    rl = RateLimiter(3, 10)
    print([rl.allow(t) for t in (1, 2, 3, 4, 12)])     # [True, True, True, False, True]

06Practice

• LeetCode 3Longest Substring Without Repeating CharactersMedium
• LeetCode 643Maximum Average Subarray I (fixed window)Easy
• LeetCode 209Minimum Size Subarray Sum (shortest valid window)Medium
• LeetCode 424Longest Repeating Character ReplacementMedium
• LeetCode 567Permutation in String (fixed window plus counts)Medium
• LeetCode 76Minimum Window SubstringHard