Sliding Window Technique: Subarray Problems

Key Insights

• Sliding window transforms O(n²) brute force subarray problems into O(n) solutions by maintaining a running computation as you traverse the data
• Fixed-size windows use a simple add-right/remove-left pattern, while variable-size windows require condition-based expansion and contraction with two pointers
• Combining sliding window with hash maps unlocks solutions for frequency counting, anagram detection, and uniqueness constraints

Introduction to Sliding Window

The sliding window technique is one of the most practical algorithmic patterns you’ll encounter in real-world programming. The concept is simple: instead of recalculating results for every possible subarray from scratch, you maintain a “window” that slides across your data, updating your computation incrementally.

Consider finding the maximum sum of any 3 consecutive elements in an array. The naive approach recalculates the sum for each starting position—O(n*k) work. With sliding window, you compute the first sum once, then slide: add the new element entering the window, subtract the element leaving. Each slide is O(1), giving you O(n) total.

Use sliding window when you’re dealing with contiguous sequences (subarrays or substrings) and need to find, count, or optimize something about them. If the problem involves “consecutive,” “contiguous,” or “substring,” sliding window should be your first thought.

Fixed-Size Window Problems

Fixed-size windows are the simpler variant. You know exactly how many elements your window contains, so the pattern is mechanical:

1. Build the initial window of size k
2. Slide right: add the incoming element, remove the outgoing element
3. Update your answer at each position

Here’s the classic maximum sum of k consecutive elements:

def max_sum_k_consecutive(nums: list[int], k: int) -> int:
    if len(nums) < k:
        return 0
    
    # Build initial window
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # Add right, remove left
        max_sum = max(max_sum, window_sum)
    
    return max_sum

The key insight is nums[i - k]—that’s the element falling out of the window as position i enters. This pattern applies to any fixed-size window problem: maximum average, minimum in window (with a deque for O(1) min tracking), or counting windows that satisfy a condition.

def count_good_subarrays(nums: list[int], k: int, threshold: int) -> int:
    """Count subarrays of size k with average >= threshold."""
    if len(nums) < k:
        return 0
    
    target_sum = threshold * k  # Avoid division
    window_sum = sum(nums[:k])
    count = 1 if window_sum >= target_sum else 0
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        if window_sum >= target_sum:
            count += 1
    
    return count

Variable-Size Window Problems

Variable-size windows are where sliding window gets interesting. The window expands when you need more elements to satisfy a condition, and contracts when you’ve found a valid window and want to minimize it (or when the window violates a constraint).

The template uses two pointers: left and right. The right pointer always advances. The left pointer advances when you need to shrink the window.

Here’s finding the smallest subarray with sum greater than or equal to a target:

def min_subarray_len(target: int, nums: list[int]) -> int:
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(nums)):
        current_sum += nums[right]  # Expand window
        
        while current_sum >= target:  # Valid window found
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]  # Contract window
            left += 1
    
    return min_length if min_length != float('inf') else 0

The outer loop expands; the inner loop contracts. This is still O(n) because each element is added once and removed at most once. The left pointer never moves backward.

The tricky part is knowing when to use while vs if for contraction. Use while when you want to find the minimum valid window (keep shrinking while valid). Use if when you’re counting or need exactly one contraction per expansion.

Window with Hash Map/Set

Many sliding window problems require tracking element frequencies or ensuring uniqueness. This is where hash maps and sets become essential companions.

Longest Substring Without Repeating Characters

This classic problem demonstrates using a set to track window contents:

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

An optimization: instead of shrinking one character at a time, store each character’s last seen index and jump directly:

def length_of_longest_substring_optimized(s: str) -> int:
    char_index = {}
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Find All Anagrams in a String

This problem combines fixed-size windows with frequency counting:

from collections import Counter

def find_anagrams(s: str, p: str) -> list[int]:
    if len(p) > len(s):
        return []
    
    p_count = Counter(p)
    window_count = Counter(s[:len(p)])
    result = []
    
    if window_count == p_count:
        result.append(0)
    
    for i in range(len(p), len(s)):
        # Add new character
        window_count[s[i]] += 1
        
        # Remove old character
        old_char = s[i - len(p)]
        window_count[old_char] -= 1
        if window_count[old_char] == 0:
            del window_count[old_char]
        
        if window_count == p_count:
            result.append(i - len(p) + 1)
    
    return result

The comparison window_count == p_count is O(26) for lowercase letters—effectively constant. For a more efficient approach, track how many characters have matching counts:

def find_anagrams_optimized(s: str, p: str) -> list[int]:
    if len(p) > len(s):
        return []
    
    p_count = Counter(p)
    window_count = Counter()
    result = []
    matches = 0
    required = len(p_count)
    
    for i, char in enumerate(s):
        # Add character to window
        window_count[char] += 1
        if window_count[char] == p_count.get(char, 0):
            matches += 1
        elif window_count[char] == p_count.get(char, 0) + 1:
            matches -= 1
        
        # Remove character if window exceeds size
        if i >= len(p):
            old_char = s[i - len(p)]
            if window_count[old_char] == p_count.get(old_char, 0):
                matches -= 1
            elif window_count[old_char] == p_count.get(old_char, 0) + 1:
                matches += 1
            window_count[old_char] -= 1
        
        if matches == required:
            result.append(i - len(p) + 1)
    
    return result

Common Patterns and Templates

Here’s a reusable template for variable-size sliding window problems:

def sliding_window_template(data, condition_fn, update_fn, result_fn):
    """
    Generic sliding window template.
    
    condition_fn(window_state) -> bool: Should we contract?
    update_fn(window_state, element, is_adding) -> None: Update state
    result_fn(window_state, left, right) -> Any: Extract result
    """
    left = 0
    window_state = {}  # Or whatever state you need
    result = None
    
    for right, element in enumerate(data):
        update_fn(window_state, element, is_adding=True)
        
        while condition_fn(window_state):
            result = result_fn(window_state, left, right, result)
            update_fn(window_state, data[left], is_adding=False)
            left += 1
    
    return result

Edge cases to always handle:

• Empty input: Return appropriate default (0, empty list, etc.)
• Window larger than array: Check len(nums) < k upfront
• Negative numbers: They break monotonicity assumptions—sum can decrease as window grows
• All elements same: Test your uniqueness logic

Complexity Analysis

Sliding window typically achieves O(n) time complexity. The key insight: even with nested loops, each element is processed at most twice (once when entering, once when leaving).

Space complexity varies:

• Fixed window, no auxiliary structure: O(1)
• With hash map: O(k) where k is window size or alphabet size
• With deque for min/max: O(k)

Benchmark comparison for finding max sum of k elements in a 1M element array:

That’s a 50x speedup, and the gap widens with larger k values.

Practice Problems and Variations

Organized by difficulty for deliberate practice:

Easy:

• Maximum Average Subarray I (LeetCode 643)
• Contains Duplicate II (LeetCode 219)

Medium:

• Longest Substring Without Repeating Characters (LeetCode 3)
• Minimum Size Subarray Sum (LeetCode 209)
• Find All Anagrams in a String (LeetCode 438)
• Permutation in String (LeetCode 567)
• Fruit Into Baskets (LeetCode 904)

Hard:

• Minimum Window Substring (LeetCode 76)
• Sliding Window Maximum (LeetCode 239)
• Substring with Concatenation of All Words (LeetCode 30)

Related techniques worth studying:

• Two pointers: Similar but pointers can move independently, not necessarily maintaining a window
• Prefix sums: When you need arbitrary range sums, not just contiguous windows
• Monotonic deque: For tracking min/max in sliding window in O(1)

Master sliding window and you’ll recognize it instantly in interviews and production code. The pattern is everywhere: rate limiting, moving averages, stream processing, and network packet analysis all use variations of this fundamental technique.