🪟 Sliding Window Pattern

The go-to pattern for subarray/substring problems.

TL;DR

Sliding window maintains a contiguous range over array/string, avoiding O(n²) recomputation.

"Maximum subarray of size K" → Fixed window
"Longest substring with at most K distinct" → Variable window

Visual Intuition

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2]
        └──window──┘
                    └──window──┘  (slide right)

Instead of recalculating sum each time, we:

• Add new element entering window
• Remove element leaving window

Result: O(n) instead of O(n × k)

---

Fixed-Size Window

Template

def fixed_window(arr, k):
    window_sum = sum(arr[:k])  # Initial window
    result = window_sum
    
    for i in range(k, len(arr)):
        # Slide: remove left, add right
        window_sum += arr[i] - arr[i - k]
        result = max(result, window_sum)
    
    return result

Problem: Maximum Sum Subarray of Size K

def max_sum_subarray(nums: list[int], k: int) -> int:
    if len(nums) < k:
        return 0
    
    # Initialize first window
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Slide window
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# nums = [2, 1, 5, 1, 3, 2], k = 3
# Window [2,1,5] = 8
# Window [1,5,1] = 7
# Window [5,1,3] = 9 ← max
# Window [1,3,2] = 6
# Answer: 9

---

Problem: Find All Anagrams

Find all start indices of anagrams of pattern in string.

from collections import Counter

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

# s = "cbaebabacd", p = "abc"
# Anagrams at: [0, 6] ("cba" and "bac")

---

Variable-Size Window

Template

def variable_window(arr):
    left = 0
    result = 0
    window_state = {}  # Or counter, sum, etc.
    
    for right in range(len(arr)):
        # 1. Expand: Add arr[right] to window
        update_window(window_state, arr[right])
        
        # 2. Contract: While window is invalid
        while is_invalid(window_state):
            remove_from_window(window_state, arr[left])
            left += 1
        
        # 3. Update result
        result = max(result, right - left + 1)
    
    return result

---

Problem: Longest Substring Without Repeating Characters

The classic variable-window problem.

def length_of_longest_substring(s: str) -> int:
    char_index = {}  # char -> last seen index
    max_length = 0
    left = 0
    
    for right, char in enumerate(s):
        # If char in window, shrink
        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

# "abcabcbb" → 3 ("abc")
# "bbbbb" → 1 ("b")
# "pwwkew" → 3 ("wke")

Visualization:

s = "abcabcbb"

Step 1: [a]bcabcbb       len=1, left=0
Step 2: [ab]cabcbb       len=2, left=0
Step 3: [abc]abcbb       len=3, left=0
Step 4: a[bca]bcbb       len=3, left=1 (saw 'a' again)
Step 5: ab[cab]cbb       len=3, left=2 (saw 'b' again)
Step 6: abc[abc]bb       len=3, left=3 (saw 'c' again)
Step 7: abca[bc]bb       len=2, left=5 (saw 'b' again)
Step 8: abcab[cb]b       len=2, left=6 (saw 'b' again)

---

Problem: Minimum Window Substring

Find smallest substring containing all characters of pattern.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    
    target = Counter(t)
    required = len(target)  # Unique chars needed
    
    window = {}
    formed = 0  # Unique chars with required count
    
    result = (float('inf'), 0, 0)  # (length, left, right)
    left = 0
    
    for right, char in enumerate(s):
        # Expand window
        window[char] = window.get(char, 0) + 1
        
        if char in target and window[char] == target[char]:
            formed += 1
        
        # Contract while valid
        while formed == required:
            # Update result
            if right - left + 1 < result[0]:
                result = (right - left + 1, left, right)
            
            # Shrink from left
            left_char = s[left]
            window[left_char] -= 1
            
            if left_char in target and window[left_char] < target[left_char]:
                formed -= 1
            
            left += 1
    
    return "" if result[0] == float('inf') else s[result[1]:result[2] + 1]

# s = "ADOBECODEBANC", t = "ABC"
# Output: "BANC"

---

Problem: Maximum Consecutive Ones III

Max consecutive 1s with at most k flips.

def longest_ones(nums: list[int], k: int) -> int:
    left = 0
    zeros = 0
    max_length = 0
    
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        
        # Too many zeros, shrink window
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

# nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
# Output: 6 (flip indices 5 and 10)

---

Pattern Recognition

---

Common Variations

At Most K Distinct Characters

def longest_substring_k_distinct(s: str, k: int) -> int:
    char_count = {}
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        char_count[char] = char_count.get(char, 0) + 1
        
        while len(char_count) > k:
            left_char = s[left]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

Subarray Sum Equals K

def subarray_sum(nums: list[int], k: int) -> int:
    # Note: This uses prefix sum + HashMap, not pure sliding window
    # Because negative numbers break the monotonic property
    prefix_count = {0: 1}
    current_sum = 0
    count = 0
    
    for num in nums:
        current_sum += num
        
        if current_sum - k in prefix_count:
            count += prefix_count[current_sum - k]
        
        prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
    
    return count

Interview Tip

Sliding window only works when the window has a monotonic property:

• All positive numbers → sum increases as window grows
• Distinct count increases as window grows

With negative numbers, use prefix sum + HashMap instead.

---

Complexity Analysis

Type	Time	Space
Fixed Window	O(n)	O(1) or O(k)
Variable Window	O(n)	O(k) where k = unique elements

Why O(n)? Each element enters the window once and exits once.

---

Practice Problems

Problem	Difficulty	Type
Max Sum Subarray of Size K	Easy	Fixed
Find All Anagrams	Medium	Fixed
Longest Substring Without Repeating	Medium	Variable
Minimum Window Substring	Hard	Variable
Longest Repeating Character Replacement	Medium	Variable
Maximum Consecutive Ones III	Medium	Variable
Fruit Into Baskets	Medium	Variable
Permutation in String	Medium	Fixed

---

Quick Reference

# Fixed Window
for i in range(k, len(arr)):
    window_sum += arr[i] - arr[i-k]

# Variable Window (maximize)
for right in range(len(arr)):
    add(arr[right])
    while invalid():
        remove(arr[left])
        left += 1
    result = max(result, right - left + 1)

# Variable Window (minimize)
for right in range(len(arr)):
    add(arr[right])
    while valid():
        result = min(result, right - left + 1)
        remove(arr[left])
        left += 1

---

---

Next: Binary Search → - The O(log n) superpower.