When the pattern is unsuitable

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

Sliding windows need monotone boundary reasoning, not merely contiguous input. Negative sums, unrestricted median state, or validity that flips unpredictably may require prefix maps, heaps, or other structures.

Work through an example

In [3,-2,5], sum≥4 is nonmonotone under growth/shrink. For exact target sums with negatives, count earlier prefix sums instead.

Time and space complexity

Alternative prefix hashing gives expected O(n) time/O(n) space for exact-sum counts.

Why it works

Never discard a start unless it is provably irrelevant to every future candidate under the rule.

Common mistakes

Contiguous alone does not imply sliding window.
A maximum can require a monotonic deque rather than a rolling scalar.

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