Sliding Window Technique in Python: Fixed and Variable Windows

A ferry operator has ten days of ticket sales and wants the best three consecutive days to plan extra sailings. The obvious loop sums three numbers for every starting day. But day 4's total shares two of its three days with day 3's total. Recomputing them is wasted work, and the sliding window is the technique that stops wasting it: keep one running answer, add what enters, subtract what leaves.

Fixed-size window: one in, one out

Compute the first window directly. Then for every later position, the new total is the old total plus the entering value minus the leaving value. The window slides across the array in O(n) regardless of its size k, where the recompute-everything version costs O(n * k).

def best_stretch(sales, days):
    """Highest total over any run of `days` consecutive days. Returns (total, start_index)."""
    window = sum(sales[:days])
    best, best_start = window, 0
    for end in range(days, len(sales)):
        window += sales[end] - sales[end - days]     # one in, one out
        if window > best:
            best, best_start = window, end - days + 1
    return best, best_start


ferry = [12, 30, 25, 8, 41, 39, 5, 18, 22, 27]
print(best_stretch(ferry, 3))

(88, 3)

The best run is days 3 to 5 (8 + 41 + 39 = 88). The index of the window's start is end - days + 1: if you are off by one here, you report the right total at the wrong place.

Variable-size window: grow, then shrink

Often the window size is the answer. A courier wants the shortest run of consecutive parcels whose combined weight reaches a quota. The right edge always moves forward, taking in one parcel. As long as the quota is met, record the length and shrink from the left. Each index enters the window once and leaves once, so the total work is O(n) even though there is a loop inside a loop.

def shortest_run_reaching(parcels, quota):
    """Shortest contiguous run of parcel weights whose sum is >= quota (all weights positive).
    Returns (length, start) or None."""
    left = 0
    total = 0
    best = None
    for right, weight in enumerate(parcels):
        total += weight                    # grow: take in the right edge
        while total >= quota:              # shrink while the condition still holds
            length = right - left + 1
            if best is None or length < best[0]:
                best = (length, left)
            total -= parcels[left]
            left += 1
    return best


print(shortest_run_reaching([4, 2, 9, 1, 1, 7, 3, 2], 11))
print(shortest_run_reaching([4, 2, 9, 1, 1, 7, 3, 2], 40))

(2, 1)
None

The first answer, length 2 starting at index 1, is the pair 2 + 9 = 11. Notice that the shrink step is a while, not an if: after taking in one big parcel, you may be able to drop several from the left and still meet the quota.

When the window needs memory: a dict inside

A window total is easy to maintain with one number. Other conditions need more bookkeeping. Suppose an operations dashboard wants the longest stretch of consecutive log lines that touches at most two distinct services. The window keeps a count per service; when the number of distinct keys exceeds two, shrink from the left until it does not.

def longest_two_service_run(calls):
    """Longest run of consecutive log lines that touches at most 2 distinct services."""
    counts = {}
    left = 0
    best = (0, 0)                              # (length, start)
    for right, service in enumerate(calls):
        counts[service] = counts.get(service, 0) + 1
        while len(counts) > 2:                 # invariant broken: shrink from the left
            gone = calls[left]
            counts[gone] -= 1
            if counts[gone] == 0:
                del counts[gone]               # forget services that left the window
            left += 1
        if right - left + 1 > best[0]:
            best = (right - left + 1, left)
    length, start = best
    return calls[start:start + length]


log = ["auth", "auth", "cart", "auth", "pay", "pay", "cart", "pay", "pay", "search"]
print(longest_two_service_run(log))

['pay', 'pay', 'cart', 'pay', 'pay']

The line del counts[gone] is the one people forget. Without it a service that has fully left the window still counts as a distinct key, len(counts) never goes down, and the window collapses to nothing.

Here is the argument for O(n) that interviewers like to hear. The right pointer visits each index once. The left pointer also only moves forward and never passes the right pointer, so across the whole run it moves at most n times. The inner while loop therefore does not multiply the work; it merely spreads at most n shrink steps over the outer loop. Counting total pointer movement, rather than loop nesting, is how you analyse every window problem.

Is it a window problem? A checklist

Common mistakes

• Window length off by one. Symptom: answers one too long or short. The length of the window [left, right] is right - left + 1.
• `if` instead of `while` when shrinking. Symptom: the condition is still broken after one shrink step, giving oversized windows and wrong maxima.
• Not removing zero-count keys from the dict. Symptom: the distinct-count check never goes down and the answer is too small or zero.
• Window larger than the array. Symptom: sum(sales[:days]) quietly sums everything and the loop body never runs, so you return a wrong total with no error. Validate days <= len(sales) first.
• Using a window on non-contiguous problems. Symptom: correct on small samples, wrong on others. Windows only answer questions about consecutive elements.

How this shows up in real projects and interviews

Rolling averages, "requests in the last 60 seconds" counters and burst detection are all windows over a stream, often with a deque holding the timestamps still inside the window. Interviews phrase it as "longest substring without repeating characters", "maximum sum of a subarray of size k" or "minimum window containing all of these letters". A strong answer states the invariant the window maintains (for example, at most two distinct services), says what happens when it breaks, and gives the O(n) argument: each element enters once and leaves once. If you can say why negatives invalidate the technique, you have shown you understand it rather than memorised it. For the cost model behind those claims see Data Structures.