SDE Prep
See Pricing
On this page

Sliding Window — Fixed-Size vs. Variable-Size ​

Common Interview Questions ​

  1. Maximum Average Subarray I (LC 643)

    • Problem: Given an array, find the contiguous subarray of a given length k that has the maximum average value.
    • Sliding Window Signal: The explicit phrase "subarray of a given length k" is a direct giveaway for a fixed-size window.
    • Window State: You only need a single variable, current_sum, to track the sum of the elements in the current window.
    • Goal: Calculate the sum for the first window of size k, then slide the window one element at a time, updating the sum and the max_average at each step.

  2. Longest Substring with At Most K Distinct Characters (LC 340)

    • Problem: Find the length of the longest substring that contains at most k distinct characters.
    • Sliding Window Signal: The keywords "longest substring" combined with a property ("at most k distinct") signal a variable-size window. The size is not given; you must find it.
    • Window State: A hash map is required to keep track of the frequencies of characters currently in the window. The condition to check is len(map) <= k.
    • Goal: This is a "longest window" problem. You expand the window as much as possible and update max_len at each valid step.

  3. Find All Anagrams in a String (LC 438)

    • Problem: Given a string s and a pattern p, find all start indices of p's anagrams in s.
    • Sliding Window Signal: An anagram is a permutation, meaning it must have the same length as the pattern and the same character counts. This points to a fixed-size window of len(p).
    • Window State: You need two hash maps (or arrays): one for the target character counts in p, and one for the current window in s.
    • Goal: At each step, you compare the window's frequency map to the pattern's frequency map. If they match, you record the start index (left).

This is the most important distinction in sliding window problems. Identifying which type of window you need determines the entire structure of your loop.

Fixed-Size Window ​

The problem specifies a fixed window size, k. The window is always k elements long. This is the simpler of the two patterns.

When to Use:

  • The problem explicitly states a size k.
  • Keywords: "subarray of size k," "substring of length k."

Template & Logic: The core idea is that once the window reaches size k, you slide it forward one step at a time. In each step, you add the new element and remove the element that just fell off the left edge.

python
def fixed_window(arr, k):
    # Setup for the window's state (e.g., current_sum, counts)
    window_sum = 0
    
    for i in range(len(arr)):
        # 1. ADD the new element to the window state
        window_sum += arr[i]
        
        # 2. SLIDE once the window is full
        if i >= k:
            window_sum -= arr[i - k] # Remove the element that fell off
            
        # 3. PROCESS the window once it has reached size k
        if i >= k - 1:
            # This is where you calculate your answer
            # e.g., max_sum = max(max_sum, window_sum)
            pass
    return # your answer

Example Problem: Maximum Sum Subarray of Size K (LC 643 variation) ​

Find the maximum sum of any contiguous subarray of size k.

python
def max_sum_subarray(nums, k):
    max_so_far = float('-inf')
    window_sum = 0
    left = 0
    
    for right in range(len(nums)):
        window_sum += nums[right]
        
        # Once window has k elements, check sum and shrink
        if (right - left + 1) == k:
            max_so_far = max(max_so_far, window_sum)
            window_sum -= nums[left]
            left += 1
            
    return max_so_far if max_so_far != float('-inf') else 0

Variable-Size Window ​

The problem asks for a window that satisfies a certain property, and you need to find the longest or shortest such window. The window size is not given and will change.

When to Use:

  • The problem asks for the "longest," "shortest," or "minimum" window that meets a condition.
  • The condition is based on the contents of the window (e.g., "contains at most 2 distinct characters," "has a sum of at least S").

Template & Logic: This uses the more complex expand-and-contract strategy from basics.md. The right pointer always moves forward (expands). The left pointer only moves when a condition is broken (contracts).

Example Problem: Longest Substring with K Distinct Characters (LC 340) ​

Find the length of the longest substring that contains no more than k distinct characters.

python
from collections import defaultdict

def longest_substring_with_k_distinct(s, k):
    if k == 0:
        return 0
        
    left = 0
    max_len = 0
    char_counts = defaultdict(int)
    
    for right in range(len(s)):
        # EXPAND the window by adding the right character
        char_counts[s[right]] += 1
        
        # CONTRACT the window if the condition is violated
        while len(char_counts) > k:
            char_counts[s[left]] -= 1
            if char_counts[s[left]] == 0:
                del char_counts[s[left]]
            left += 1
            
        # UPDATE the answer after each valid expansion
        max_len = max(max_len, right - left + 1)
        
    return max_len

How the Algorithms Work ​

  • Fixed-Size: This algorithm iterates through the array while maintaining a window of a constant size k. As the right pointer moves to include a new element, the left pointer also moves to discard the oldest element, keeping the window size steady. The answer is calculated at each step once the window is full.
  • Variable-Size: This algorithm expands the window by moving the right pointer. It only contracts the window by moving the left pointer when a specific condition is violated (e.g., too many unique characters). The size of the window dynamically grows and shrinks to find the optimal length that satisfies the condition.

Tricky Parts & Decision Points ​

  1. Identifying the Type: This is the most crucial decision. Does the problem explicitly state "of size k" or "of length k"? If so, it's fixed. If it asks for the "longest," "shortest," or "smallest" subarray that meets a criteria, it's variable.
  2. Fixed-Window Off-by-One: In the fixed-window pattern, it's easy to make an off-by-one error when removing the left element. The element to remove is at index i - k, and you can only start doing this once i is at least k.
  3. Variable-Window Shrink Logic: For variable windows, you must perfectly define the while loop's condition. The loop should run as long as the window is invalid. If you get it backwards (e.g., while len(counts) <= k), your window will shrink incorrectly.