Sliding Window Algorithm: Fixed, Variable, and Window Maximum in Python

Recognize a sliding window prompt

Three signals point to the pattern. The input is a sequence, the question is about a contiguous run (a subarray, a substring, consecutive days), and the window's property can be updated cheaply when one element enters or leaves: a running sum, a frequency map, a count of violations. If the prompt says subsequence instead of substring, or lets you reorder elements, a window is usually the wrong model.

Then decide which of two shapes you have. A fixed window has its length given, k consecutive elements, so both edges move together. A variable window grows on the right and shrinks on the left to keep a condition true; it answers longest and shortest questions. Both reach O(n) for the same reason: each index enters the window once and leaves at most once.

Fixed window: maximum sum of k consecutive elements

The invariant is that window always equals the sum of the k elements ending at right. Building the first window costs O(k); each later step adds the entering value and subtracts the leaving one, so the function runs in O(n) time with O(1) extra space. Recomputing sum(nums[i:i + k]) inside the loop gives the same answer in O(n·k), which is the version an interviewer expects you to improve.

The script prints 9, then -6. The window that sums to 9 is [5, 1, 3]. The second call matters: a fixed window works with negative numbers, because nothing is decided by comparing the sum with a threshold; both edges simply advance. Validate k up front. An empty input or a k larger than the input is an edge case worth naming before you write the loop.

def max_window_sum(nums, k):
    if not 0 < k <= len(nums):
        raise ValueError("need 0 < k <= len(nums)")
    window = sum(nums[:k])                  # first full window
    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

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))
print(max_window_sum([-4, -2, -7, -1], 2))

Variable window: longest substring with at most k distinct characters

Here the window from left to right is valid when it contains at most k distinct characters. Extend right on every iteration; when the new character breaks the condition, advance left until it holds again. Record the answer only after the inner loop finishes. Updating best before restoring the invariant is a classic bug in this family. Delete keys whose count drops to zero, or len(counts) stops meaning the number of distinct characters.

The output is 3, 2, and 6: “ece” for k = 2, “aa” for k = 1, and the whole string when k = 3 covers every letter. The nested while loop looks quadratic, but left only moves forward and never passes right, so it advances at most n times across the entire run. Total pointer movement is at most 2n, which gives O(n) time, and the map holds at most k + 1 keys. Python's documentation gives dict operations as O(1) on average.

def longest_k_distinct(s, k):
    counts = {}
    left = best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > k:              # restore the invariant
            out = s[left]
            counts[out] -= 1
            if counts[out] == 0:
                del counts[out]             # len(counts) = distinct chars
            left += 1
        best = max(best, right - left + 1)  # window is valid here
    return best

print(longest_k_distinct("eceba", 2))
print(longest_k_distinct("aabbcc", 1))
print(longest_k_distinct("aabbcc", 3))

• Python docs: Time complexity of operations on built-in types

Sliding window maximum with a monotonic deque

A running sum cannot answer maximum queries, because removing the outgoing element does not tell you the new maximum. The deque stores indices whose values strictly decrease from front to back. Before appending index i, pop every back index whose value is ≤ nums[i]: those elements are older and no larger, so they can never be a window maximum again. The front is the current maximum; drop it once its index falls out of the window.

The script prints [3, 3, 5, 5, 6, 7] and [9, 8, 7]. In the second input the values only decrease, so nothing leaves from the back and every removal is an expiry at the front. Each index is appended once and popped at most once: O(n) time, O(k) space. Python's deque gives approximately O(1) appends and pops at both ends, while list.pop(0) is O(n). Lemire's 2006 paper builds a streaming max-min filter on the same monotonic structure, using double-ended queues.

from collections import deque

def window_max(nums, k):
    dq = deque()                  # indices; their values strictly decrease
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()              # dominated: can never be a maximum again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()          # front index slid out of the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_max([9, 8, 7, 6], 2))

• Python docs: collections.deque
• Daniel Lemire: Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element (arXiv)

When the window breaks: negative numbers and sum constraints

A variable window over sums relies on monotonicity: adding an element never decreases the sum and removing one never increases it. That holds only for non-negative values. With a negative number, shrinking can make the sum grow, so discarding a left index may discard a valid answer. Exact-count questions are stricter still and need strictly positive values, because a zero lets several left edges share one right edge.

The script counts subarrays that sum to 3 with both methods. For [1, 2, 1, 2] both print 3. For [3, -1, 1, 3] the window finds 3 while the true answer is 4: at the last index both [-1, 1, 3] and [3] sum to 3, and a window reports only one left edge per right edge. For [0, 3, 0] it prints 2 instead of 4 for the same reason. The prefix-sum version counts earlier prefixes equal to total − k, in O(n) time and O(n) space, and it handles any integers.

from collections import defaultdict

def window_count(nums, k):        # correct only for strictly positive nums
    left = total = count = 0
    for right, x in enumerate(nums):
        total += x
        while total > k and left <= right:
            total -= nums[left]
            left += 1
        if total == k:
            count += 1
    return count

def prefix_count(nums, k):        # any integers: count earlier prefix sums
    seen = defaultdict(int, {0: 1})
    total = count = 0
    for x in nums:
        total += x
        count += seen[total - k]
        seen[total] += 1
    return count

for nums in ([1, 2, 1, 2], [3, -1, 1, 3], [0, 3, 0]):
    print(nums, window_count(nums, 3), prefix_count(nums, 3))

How to explain a sliding window in an interview

Say the invariant before writing code: “the window holds at most k distinct characters” or “deque values decrease from front to back.” Then state when the window grows, when it shrinks, and where the answer is recorded. Finish with the amortized argument in one sentence: each index enters once and leaves once. That order gives the interviewer a correctness claim to check, not only a loop that happens to pass.

Test the cases that break naive versions: an empty input, k = 0, k larger than the length, all-equal elements, and a strictly decreasing array for the deque. If the interviewer adds negative numbers to a sum problem, explain why the window fails instead of patching it, and offer prefix sums as the replacement.

• Window length is right - left + 1, not right - left.
• Shrink with while, not if: one removal may not restore the condition.
• Store indices, not values, in the deque so you can detect expiry.
• Remove zero counts from the map so its size stays meaningful.

Practice until the invariant comes first

Rewrite each function from memory a day later, then change one rule: maximum becomes minimum, at most k distinct becomes a count of subarrays with exactly k distinct values (hint: at most k minus at most k − 1), and a sum threshold becomes a product of positive numbers. If you can state the new invariant before typing, the pattern has stuck. A spaced-repetition app such as RecallDeck can help with recalling invariants; the coding itself still belongs in your editor.

For the surrounding material, work through the data structures and algorithms question set, and use the practice platforms roundup to find timed problems for each window shape.

• 53 data structures and algorithms interview questions
• The best coding practice platforms
• Explore the backend interview track

Quick answers

Frequently asked questions