Sliding Window Pattern

What is Sliding Window?

The Sliding Window pattern maintains a dynamic window over a sequence to find optimal subarrays or substrings. It reduces nested loops from O(n²) to O(n) by reusing computations.

Quick Recognition: If you see “contiguous subarray” or “substring” + need to find max/min/count, Sliding Window is likely the answer!

Pattern Recognition Checklist

Use Sliding Window When

Problem mentions contiguous elements
Need subarray or substring
Looking for maximum/minimum length
Constraint on window (at most K, exactly K)
Can solve by expanding and shrinking

Don't Use When

Elements don’t need to be contiguous
Need all subsets (use Backtracking)
Sorted array hints (use Two Pointers)
Need position of elements (use HashMap)

Three Types of Sliding Window

When to Use

Contiguous Subarrays

Finding max/min sum, average, or product of k elements

Substring Problems

Longest/shortest substring with certain properties

Fixed Size Window

Problems asking about “exactly k” or “window of size k”

Variable Size Window

Problems with “at most k” or “minimum length”

Pattern Variations

1. Fixed Size Window

Window size remains constant throughout.

def max_sum_subarray_k(arr, k):
    """Find maximum sum of subarray with exactly k elements"""
    if len(arr) < k:
        return -1
    
    # Calculate sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # Add new, remove old
        max_sum = max(max_sum, window_sum)
    
    return max_sum

2. Variable Size Window (Expand and Shrink)

Window grows and shrinks based on conditions.

def min_subarray_sum(arr, target):
    """Find minimum length subarray with sum >= target"""
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]  # Expand window
        
        while current_sum >= target:  # Shrink while valid
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

3. Window with HashMap/Counter

Track element frequencies within the window.

def longest_substring_k_unique(s, k):
    """Longest substring with exactly k unique characters"""
    from collections import defaultdict
    
    if k == 0:
        return 0
    
    left = 0
    char_count = defaultdict(int)
    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
        
        if len(char_count) == k:
            max_length = max(max_length, right - left + 1)
    
    return max_length

Classic Problems

1. Maximum Sum Subarray of Size K

Problem: Find the maximum sum of any contiguous subarray of size k.Approach: Fixed window - slide and update sum by adding new element and removing old.Time: O(n) | Space: O(1)

2. Longest Substring Without Repeating Characters

Problem: Find length of longest substring without duplicate characters.Approach: Variable window with HashSet. Shrink when duplicate found.Time: O(n) | Space: O(min(n, m)) where m is charset size

3. Minimum Window Substring

Problem: Find smallest substring containing all characters of another string.Approach: Variable window with character frequency tracking. Expand to include all, shrink to minimize.Time: O(n + m) | Space: O(m)

4. Fruit Into Baskets

Problem: Maximum fruits you can collect with only 2 baskets (2 types).Approach: Longest subarray with at most 2 distinct elements.Time: O(n) | Space: O(1)

5. Permutation in String

Problem: Check if s2 contains a permutation of s1.Approach: Fixed window of size len(s1), compare character frequencies.Time: O(n) | Space: O(1)

Template Code

# Template 1: Fixed Window
def fixed_window_template(arr, k):
    # Initialize first window
    window_result = sum(arr[:k])
    best = window_result
    
    for i in range(k, len(arr)):
        # Slide: remove arr[i-k], add arr[i]
        window_result = window_result - arr[i-k] + arr[i]
        best = max(best, window_result)
    
    return best

# Template 2: Variable Window (At Most K Pattern)
def variable_window_template(arr, k):
    left = 0
    count = {}
    result = 0
    
    for right in range(len(arr)):
        # Expand: add arr[right] to state
        count[arr[right]] = count.get(arr[right], 0) + 1
        
        # Shrink while invalid
        while len(count) > k:
            count[arr[left]] -= 1
            if count[arr[left]] == 0:
                del count[arr[left]]
            left += 1
        
        # Update result
        result = max(result, right - left + 1)
    
    return result

# Template 3: Minimum Window (Find Smallest Valid)
def min_window_template(arr, target):
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        while current_sum >= target:  # While window is valid
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

Sliding Window Decision Tree

Is it about subarray/substring?
|
+-- YES --> Is it asking for min/max/count?
|           |
|           +-- Fixed size k? --> Fixed Window
|           |
|           +-- Variable size? 
|               |
|               +-- "At most K" --> Expand + Shrink when > K
|               |
|               +-- "At least K" --> Expand + Count valid extensions
|               |
|               +-- "Exactly K" --> AtMost(K) - AtMost(K-1)
|
+-- NO --> Consider other patterns

Common Mistakes

Avoid These Pitfalls:

Forgetting to shrink: Always shrink when window becomes invalid
Wrong window update order: Expand first, then shrink, then update result
Not handling empty result: Check for edge cases like empty input
Counting exactly K wrong: Use AtMost(K) - AtMost(K-1) trick

Debugging Checklist

When your Sliding Window solution fails:

Check Expand Logic

Are you correctly adding the new element to your window state?

Check Shrink Condition

Is the while condition correct? (> k vs >= k matters!)

Check Shrink Logic

Are you correctly removing the left element from state?

Check Result Update

Are you updating result at the right time? (Usually after shrink)

Check Edge Cases

Empty string? K = 0? All same characters?

Complexity Quick Reference

Problem Type	Time	Space	Window Type
Max sum of K elements	O(n)	O(1)	Fixed
Longest substring no repeat	O(n)	O(min(n,m))	Variable
Min window substring	O(n+m)	O(m)	Variable
Subarrays with K distinct	O(n)	O(K)	Variable
Max consecutive ones with K flips	O(n)	O(1)	Variable

Interview Problems by Company

Easy
Medium
Hard

Problem	Company	Key Concept
Max Average Subarray I	Amazon	Fixed window basics
Contains Duplicate II	Meta	Fixed window + set
Max Consecutive Ones	Google	Simple sliding
Find All Anagrams	Amazon, Meta	Fixed window + frequency

Problem	Company	Key Concept
Longest Substring No Repeat	All FAANG	Variable + HashMap
Longest Repeating Replacement	Google	Variable + count
Max Ones with K Flips	Meta	Variable window
Permutation in String	Microsoft	Fixed + frequency
Fruit Into Baskets	Google	At most 2 distinct

Problem	Company	Key Concept
Minimum Window Substring	All FAANG	Classic min window
Sliding Window Maximum	Amazon, Google	Window + Deque
Subarrays K Different	Google	Exactly K trick
Substring Concatenation	Amazon	Complex fixed window

Interview Tips

How to Explain Your Approach

Script for interviews:

“I see this is about contiguous subarrays, so I’ll use Sliding Window.”
“I’ll maintain a window with two pointers: left and right.”
“Right pointer expands the window, left pointer shrinks it.”
“I’ll track [state] to know when window is valid/invalid.”
“This gives us O(n) time since each element is visited at most twice.”

When Interviewer Says...

Interviewer Says	You Should Think
”Find contiguous subarray”	Sliding Window!
”Longest/shortest substring”	Sliding Window!
”At most K distinct”	Variable window + shrink when > K
”Exactly K”	AtMost(K) - AtMost(K-1)
“All subarrays of size K”	Fixed window
”Contains permutation”	Fixed window + frequency match

The AtMost Trick Explained

Why “Exactly K = AtMost(K) - AtMost(K-1)”?

AtMost(K) counts all windows with 0, 1, 2, … K distinct elements
AtMost(K-1) counts all windows with 0, 1, 2, … K-1 distinct elements
Subtracting gives us ONLY windows with exactly K distinct elements

This trick works because directly counting “exactly K” is hard, but “at most K” is easy!

The “Exactly K” Trick

from collections import defaultdict

def subarrays_exactly_k_distinct(arr, k):
    """Count subarrays with exactly k distinct elements"""
    def at_most_k(arr, k):
        left = 0
        count = defaultdict(int)
        result = 0
        
        for right in range(len(arr)):
            count[arr[right]] += 1
            
            while len(count) > k:
                count[arr[left]] -= 1
                if count[arr[left]] == 0:
                    del count[arr[left]]
                left += 1
            
            result += right - left + 1
        
        return result
    
    return at_most_k(arr, k) - at_most_k(arr, k - 1)

Practice Problems

Problem	Difficulty	Link
Maximum Average Subarray I	Easy	LeetCode 643
Longest Substring Without Repeating	Medium	LeetCode 3
Minimum Window Substring	Hard	LeetCode 76
Sliding Window Maximum	Hard	LeetCode 239
Subarrays with K Different Integers	Hard	LeetCode 992

Practice Roadmap

Day 1: Fixed Window

Solve: Max Average Subarray, Contains Duplicate II
Focus: Understanding the slide (add new, remove old)

Day 2: Variable Window - Max

Solve: Longest Substring Without Repeat, Longest Repeating Replacement
Focus: Expand + shrink when invalid

Day 3: Variable Window - Min

Solve: Minimum Size Subarray Sum, Minimum Window Substring
Focus: Shrink while valid (opposite of max)

Day 4: Exactly K Problems

Solve: Subarrays with K Different Integers
Focus: The AtMost(K) - AtMost(K-1) trick

Memory Trick: SLIDE

Remember SLIDE for Sliding Window:

Subarray/Substring problem?
Length constraints?
Iterate with two pointers?
Dynamic window size?
Expand and shrink?

Interview Tip: When you see “contiguous”, “subarray”, or “substring” with an optimization goal, Sliding Window should be your first thought.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Sliding Window?

Pattern Recognition Checklist

Use Sliding Window When

Don't Use When

Three Types of Sliding Window

When to Use

Contiguous Subarrays

Substring Problems

Fixed Size Window

Variable Size Window

Pattern Variations

1. Fixed Size Window

2. Variable Size Window (Expand and Shrink)

3. Window with HashMap/Counter

Classic Problems

Template Code

Sliding Window Decision Tree

Common Mistakes

Debugging Checklist

Complexity Quick Reference

Interview Problems by Company

Interview Tips

The “Exactly K” Trick

Practice Problems

Practice Roadmap

Memory Trick: SLIDE

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

​What is Sliding Window?

​Pattern Recognition Checklist

Use Sliding Window When

Don't Use When

​Three Types of Sliding Window

​When to Use

Contiguous Subarrays

Substring Problems

Fixed Size Window

Variable Size Window

​Pattern Variations

​1. Fixed Size Window

​2. Variable Size Window (Expand and Shrink)

​3. Window with HashMap/Counter

​Classic Problems

​Template Code

​Sliding Window Decision Tree

​Common Mistakes

​Debugging Checklist

​Complexity Quick Reference

​Interview Problems by Company

​Interview Tips

​The “Exactly K” Trick

​Practice Problems

​Practice Roadmap

​Memory Trick: SLIDE

What is Sliding Window?

Pattern Recognition Checklist

Three Types of Sliding Window

When to Use

Pattern Variations

1. Fixed Size Window

2. Variable Size Window (Expand and Shrink)

3. Window with HashMap/Counter

Classic Problems

Template Code

Sliding Window Decision Tree

Common Mistakes

Debugging Checklist

Complexity Quick Reference

Interview Problems by Company

Interview Tips

The “Exactly K” Trick

Practice Problems

Practice Roadmap

Memory Trick: SLIDE