Sliding Window

The sliding window technique maintains a “window” (subarray or substring) that slides across the data. You expand the right boundary to grow the window and shrink the left boundary to maintain constraints.

Why It Matters

Sliding window turns O(n^2) brute-force substring/subarray problems into O(n). It’s the go-to pattern for “find the longest/shortest subarray/substring that satisfies X.”

Two Types

Fixed-Size Window

Window size is given (e.g., “max sum of subarray of size k”).

def max_sum_subarray(nums: list[int], k: int) -> int:
    """Maximum sum of any contiguous subarray of size k."""
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # slide: add right, remove left
        best = max(best, window_sum)
    return best
 
assert max_sum_subarray([2, 1, 5, 1, 3, 2], 3) == 9  # [5, 1, 3]

Variable-Size Window

Window grows and shrinks based on a condition.

def min_subarray_sum(nums: list[int], target: int) -> int:
    """Shortest subarray with sum >= target. Returns 0 if none."""
    left = 0
    current_sum = 0
    min_len = float('inf')
 
    for right in range(len(nums)):
        current_sum += nums[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
 
    return min_len if min_len != float('inf') else 0
 
assert min_subarray_sum([2, 3, 1, 2, 4, 3], 7) == 2  # [4, 3]
 
def longest_unique_substring(s: str) -> int:
    """Length of longest substring without repeating characters."""
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best
 
assert longest_unique_substring("abcabcbb") == 3  # "abc"
assert longest_unique_substring("bbbbb") == 1      # "b"

The Template

def sliding_window(data, ...):
    left = 0
    state = ...  # running sum, frequency map, etc.
 
    for right in range(len(data)):
        # Expand: add data[right] to state
        ...
 
        # Shrink: while constraint is violated
        while constraint_violated(state):
            # Remove data[left] from state
            ...
            left += 1
 
        # Update answer (longest/shortest/count)
        ...

Common Problems

Problem	Window Tracks
Max sum subarray of size k	Running sum
Longest substring without repeats	Character set/map
Minimum window substring	Character frequency
Longest subarray with sum ⇐ k	Running sum
Count subarrays with at most k distinct	Frequency map

Related

• Two Pointers — sliding window is a two-pointer variant
• Hash Tables — often used to track window contents
• Dynamic Programming — some window problems can also be solved with DP
• Arrays — sliding window operates on sequential data