Sliding Window

Imagine a window that slides across your array, keeping track of what's inside. Instead of recalculating everything from scratch each time, you just update what enters and leaves the window. That's O(n) instead of O(n²).

The Core Idea

You maintain a "window" - a contiguous subarray or substring. As you slide it across your data, you efficiently update your answer by only considering what changed: the element leaving the window and the element entering it.

Two Types of Windows

1. Fixed-Size Window

Window size is given. Find max sum of k consecutive elements:

def maxSumSubarray(arr, k):
    # Initialize first window
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide the window
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # Add new, remove old
        max_sum = max(max_sum, window_sum)

    return max_sum

2. Variable-Size Window

Window grows and shrinks based on conditions:

left = 0
for right in range(len(arr)):
    # Expand window - add arr[right]

    while window_is_invalid:
        # Shrink window - remove arr[left]
        left += 1

    # Update answer with current valid window

Real Example: Longest Substring Without Repeating

Find the length of the longest substring with all unique characters. This is the classic variable window problem:

def lengthOfLongestSubstring(s):
    seen = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        # Shrink until no duplicate
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

Real Example: Minimum Window Substring

Find the smallest window containing all characters of a target string. This is a harder variant:

def minWindow(s, t):
    need = Counter(t)
    missing = len(t)
    left = start = end = 0

    for right, char in enumerate(s, 1):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        if missing == 0:  # Valid window
            # Shrink from left
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            # Update result
            if end == 0 or right - left < end - start:
                start, end = left, right

Common Patterns

• Use a hash map to track character frequencies in the window
• Track a "valid" condition - when is the window acceptable?
• Update answer inside or after the shrinking loop, depending on the problem