Pattern 3 — Sliding Window

The idea, in one line

Keep a moving range over your list, and reuse the last answer instead of recounting from scratch. That's the sliding window pattern, and it turns a slow double loop into a single pass.

How to spot it

The task asks for the longest, shortest, maximum sum, or best run of items that sit next to each other — a stretch of the list, not a scattered pick. These words give it away:

• window — a fixed span you slide along
• consecutive — items in a row, no gaps
• substring — a run of characters, not scattered letters

Two flavours

Fixed window of size k: add up the first k items, then slide by adding the item coming in and subtracting the one going out — window += arr[i] - arr[i-k] — keeping track of the best you've seen.

Variable window: grow the right edge to let more in, and when a rule breaks — a duplicate, or a sum over budget — shrink from the left until the rule holds again. A dict or set remembers what's currently inside.

See it work

# Fixed window: most total requests in any 3-minute span
def max_window_sum(counts, k):
    window = sum(counts[:k])
    best = window
    for i in range(k, len(counts)):
        window += counts[i] - counts[i - k]   # add new, drop old
        best = max(best, window)
    return best

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))  # 9  (5+1+3)

Read it top to bottom: sum the first three, then each step add the incoming minute and subtract the outgoing one. You never re-add the whole window — only the two numbers that changed.

# Variable window: longest run with no repeating character
def longest_unique(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1   # shrink past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))            # 3  ('abc')

Advanced — the mental model

The whole speed-up comes from one habit: instead of re-reading the entire window every step, you only account for the one element entering and the one leaving. That's the difference between checking every pair and taking a single walk — O(n) instead of O(n²).

Grounded in the GeeksforGeeks 'Sliding Window Technique' tutorial