Fixed-size sliding windows

What is a sliding window?

A window is a consecutive part of a sequence. Sliding it means moving its boundaries as you examine the sequence. For a fixed-size window, one item leaves and one enters at each move. Keeping a running total or count lets you reuse work instead of rebuilding it every time.

Example: The size-3 windows in [2, 1, 4, 3] are [2, 1, 4] and [1, 4, 3]. Their totals are 7 and 8. To get the second total, subtract 2 and add 3.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Hash maps and sets

Understand the idea

A fixed-size window keeps exactly k consecutive elements. Compute the first aggregate, then remove the outgoing value and add the incoming one. Validate k and initialize best from a real window.

Work through an example

For [2,1,5,1,3,2], k=3, sums are 8,7,9,6. The second is 8-2+1=7. All-negative input still requires a negative best.

Time and space complexity

O(n) time/O(1) auxiliary state in the lab's indexed initialization.

Why it works

Current equals the sum of the active k positions.

Common mistakes

best=0 fails negative windows.
A slice used to initialize the sum allocates O(k) extra space.

Chapter lab · Python implementation

A window represents a contiguous active interval. Reuse its overlapping state when advancing boundaries. The lab finds the longest substring with distinct characters; a fixed-size sum example contrasts automatic eviction with condition-based shrinking. Bounds below count code points, not user-visible grapheme clusters.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def max_window_sum(values,k):
    if not 1<=k<=len(values):
        raise ValueError('invalid k')
    current=0
    for i in range(k):
        current+=values[i]
    best=current
    for right in range(k,len(values)):
        current+=values[right]-values[right-k]
        best=max(best,current)
    return best

def longest_unique(text):
    counts={}
    left=best=0
    for right,char in enumerate(text):
        counts[char]=counts.get(char,0)+1
        while counts[char]>1:
            old=text[left]
            counts[old]-=1
            if counts[old]==0:
                del counts[old]
            left+=1
        best=max(best,right-left+1)
    return best

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert max_window_sum([2,1,5,1,3,2],3)==9
assert max_window_sum([-5,-2,-8],2)==-7
assert longest_unique('abca')==3
assert longest_unique('')==0
assert longest_unique('abba')==2

CHECK YOUR UNDERSTANDING