Sliding Window Fundamentals

What is the Sliding Window Technique?

The sliding window is an algorithmic technique used to efficiently process contiguous subsets ("windows") of a sequence — such as an array or string — by maintaining a running computation rather than recalculating from scratch at each position. Instead of re-examining every element in a window when it moves one step, the algorithm simply adds the new element entering the window and removes the element leaving it, reducing per-step cost from O(k) to O(1).

This pattern transforms many brute-force O(n×k) problems into O(n) solutions, making it one of the most important techniques in both algorithm design and real-world data stream processing.

The Basic Concept

Instead of recalculating everything:
Window moves 1 position at a time

Old data:     Remove
              ↓
[1, 2, 3, 4, 5, 6, 7]
   ───────
   Window
              ↑
New data:     Add

Calculation:
sum(new_window) = sum(old_window) - removed + added

Time Complexity

Naive: O(n * k)
- For each position: recalculate entire window
- n positions × k size = n*k operations

Sliding window: O(n)
- Calculate first window: O(k)
- Slide n times: O(1) each
- Total: O(k) + O(n) = O(n)

Example:
Array of 1M elements, window size 1000:
Naive: 1,000,000,000 operations
Sliding: 1,001,000 operations
1000x faster!

Two Types

Fixed-Size Window

Window size known and constant

Example: Find max sum of 3 consecutive numbers
[1, 2, 3, 4, 5]
[1, 2, 3] → sum = 6
[2, 3, 4] → sum = 9
[3, 4, 5] → sum = 12 (max)

Variable-Size Window

Window size expands/contracts based on condition

Example: Longest substring without repeating characters
"abcabcbb"
"a" → "ab" → "abc" → "cab" (skip 'a') → "cab" → "abc"

Template Pattern

Most sliding window problems follow this structure:

def sliding_window(data, condition):
    window = deque()
    left = 0
    result = 0
    
    for right in range(len(data)):
        # Add new element
        window.append(data[right])
        
        # Shrink window if condition violated
        while not condition(window):
            window.popleft()
            left += 1
        
        # Update result
        result = max(result, len(window))
    
    return result

Classic Problems

1. Maximum sum subarray of size k
2. Longest substring without repeating chars
3. Contains duplicate (within distance k)
4. Minimum window substring
5. Fruit into baskets
6. Longest repeating character replacement