Sliding Window Pattern Explained with Examples

What is Sliding Window?

The sliding window technique is a method for solving problems involving contiguous sequences (subarrays or substrings). Instead of recalculating everything for each position, we "slide" a window across the data, updating our calculation incrementally.

The Core Idea

Imagine you're calculating the sum of every 3 consecutive elements in an array:

Array: [1, 3, 2, 6, 4, 8]

Naive approach (recalculate each time):
  Window 1: 1 + 3 + 2 = 6
  Window 2: 3 + 2 + 6 = 11
  Window 3: 2 + 6 + 4 = 12
  ...

With sliding window, we add the new element and remove the old one:

Window 1: 1 + 3 + 2 = 6
Window 2: 6 - 1 + 6 = 11  (remove 1, add 6)
Window 3: 11 - 3 + 4 = 12 (remove 3, add 4)

This reduces time from O(n × k) to O(n).

Fixed Size Window

When the window size is predetermined.

Template

def fixed_window(arr, k):
    n = len(arr)
    if n < k:
        return None
    
    # Initialize first window
    window_sum = sum(arr[:k])
    result = window_sum
    
    # Slide the window
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        result = max(result, window_sum)
    
    return result

Example: Maximum Average Subarray

Find the contiguous subarray of length k with the maximum average.

def find_max_average(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum / k

Variable Size Window

When the window size changes based on conditions. This is more common in interviews.

Template

def variable_window(s):
    left = 0
    result = 0
    window = {}  # or other data structure
    
    for right in range(len(s)):
        # Expand window: add s[right]
        update_window(window, s[right])
        
        # Contract window while invalid
        while not is_valid(window):
            remove_from_window(window, s[left])
            left += 1
        
        # Update result
        result = max(result, right - left + 1)
    
    return result

Example: Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    char_index = {}  # Last seen index of each character
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        # If char was seen and is in current window
        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

Universal Template

Here's a general template that works for most sliding window problems:

def sliding_window(s, pattern_or_condition):
    from collections import defaultdict
    
    window = defaultdict(int)
    required = defaultdict(int)
    
    # Build required (if matching a pattern)
    for char in pattern_or_condition:
        required[char] += 1
    
    left = 0
    formed = 0  # Conditions satisfied
    result = float('inf')  # or 0 for maximum
    result_window = (0, 0)
    
    for right in range(len(s)):
        # Add right character to window
        char = s[right]
        window[char] += 1
        
        # Check if this char satisfies a condition
        if char in required and window[char] == required[char]:
            formed += 1
        
        # Try to contract window
        while formed == len(required):
            # Update result
            if right - left + 1 < result:
                result = right - left + 1
                result_window = (left, right)
            
            # Remove left character
            left_char = s[left]
            window[left_char] -= 1
            if left_char in required and window[left_char] < required[left_char]:
                formed -= 1
            left += 1
    
    return result_window

Solved Examples

Example 1: Minimum Size Subarray Sum

Find the minimal length subarray with sum ≥ target.

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

Example 2: Longest Substring with At Most K Distinct Characters

def longest_substring_k_distinct(s, k):
    from collections import defaultdict
    
    char_count = defaultdict(int)
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        char_count[s[right]] += 1
        
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

Practice Problems

1. Easy:*
2. Maximum Average Subarray I
3. Contains Duplicate II

1. Medium:*
2. Longest Substring Without Repeating Characters
3. Minimum Size Subarray Sum
4. Permutation in String
5. Longest Repeating Character Replacement

1. Hard:*
2. Minimum Window Substring
3. Sliding Window Maximum

Key Takeaways

1. Fixed vs Variable:* Know which type you need
2. What to track:* Sum, count, frequency map, etc.
3. When to shrink:* Define clear shrinking conditions
4. Update result:* At each valid window state
5. Edge cases:* Empty input, window larger than input

Master sliding window, and you'll efficiently solve a whole category of interview problems!