Complexity Analysis
Single pass through the array. Each element is added once and removed once. Only a few variables needed to track the window state.
Recognize This Pattern When...
Pattern Signals
- "Subarray of size k" or "window of length k"
- Find maximum/minimum/average over all k-length subarrays
- Contiguous elements with a known, fixed window size
- "Every k consecutive elements"
- Problem specifies an exact window size, not a constraint
Preconditions
- Window size k is given explicitly in the problem
- Working with contiguous subarrays (not subsequences)
- Aggregate operation (sum, count, max) can be updated incrementally
When NOT to Use
- Window size varies based on a condition (use variable sliding window)
- Looking for non-contiguous elements (subsequences)
- k > n (array smaller than window size)
- Need to find optimal k, not given k
Why It Works
Instead of recalculating the sum/count for every k-element window from scratch (O(n*k)), we reuse the previous calculation. When the window slides right by one position, we add the new element and remove the element that fell off the left side. This transforms repeated O(k) work into O(1) updates.
The Analogy
Think of a train with exactly k cars passing by a station. As a new car enters the station view, the last car exits. You don't need to recount all cars—just add one and subtract one from your running total.
The Canonical Problem
Maximum Average Subarray I
easyGiven an integer array nums and an integer k, find a contiguous subarray of length k that has the maximum average value. Return the maximum average.
Solve on LeetCodeAlgorithm Template
Generic template you can adapt to most sliding window (fixed size) problems.
def fixed_sliding_window(nums, k):
# 1. Build first window
window_sum = sum(nums[:k])
max_sum = window_sum
# 2. Slide window across array
for i in range(k, len(nums)):
window_sum += nums[i] # Add right element
window_sum -= nums[i - k] # Remove left element
max_sum = max(max_sum, window_sum)
return max_sumImplementations
Complete examples with explanations. Copy-paste and adapt to your problem.
def find_max_average(nums: list[int], k: int) -> float:
"""
Find the maximum average of any k-length subarray.
Time: O(n), Space: O(1)
"""
# Build first window
window_sum = sum(nums[:k])
max_sum = window_sum
# Slide window
for i in range(k, len(nums)):
window_sum += nums[i] # Add new element
window_sum -= nums[i - k] # Remove old element
max_sum = max(max_sum, window_sum)
return max_sum / k
# Example usage
nums = [1, 12, -5, -6, 50, 3]
k = 4
print(find_max_average(nums, k)) # 12.75 (subarray [12, -5, -6, 50])
# Variant: Find All Anagrams (frequency map version)
def find_anagrams(s: str, p: str) -> list[int]:
"""Find all start indices where anagrams of p occur in s."""
if len(p) > len(s):
return []
from collections import Counter
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 right character
window[s[i]] += 1
# Remove left character
left_char = s[i - len(p)]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == p_count:
result.append(i - len(p) + 1)
return resultPython implementation showing the sum variant for Maximum Average and the frequency-map variant for anagram detection. Both follow the same add-right, remove-left pattern.
/**
* Find the maximum average of any k-length subarray.
*
* Time: O(n), Space: O(1)
*/
function findMaxAverage(nums, k) {
// Build first window
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += nums[i];
}
let maxSum = windowSum;
// Slide window
for (let i = k; i < nums.length; i++) {
windowSum += nums[i]; // Add right element
windowSum -= nums[i - k]; // Remove left element
maxSum = Math.max(maxSum, windowSum);
}
return maxSum / k;
}
// Example usage
const nums = [1, 12, -5, -6, 50, 3];
const k = 4;
console.log(findMaxAverage(nums, k)); // 12.75
// Variant: Check if permutation exists in string
function checkInclusion(s1, s2) {
if (s1.length > s2.length) return false;
const count = new Array(26).fill(0);
const k = s1.length;
// Build target count from s1
for (const c of s1) {
count[c.charCodeAt(0) - 97]++;
}
// Build first window from s2
const window = new Array(26).fill(0);
for (let i = 0; i < k; i++) {
window[s2.charCodeAt(i) - 97]++;
}
if (arraysEqual(count, window)) return true;
// Slide window
for (let i = k; i < s2.length; i++) {
window[s2.charCodeAt(i) - 97]++; // Add right
window[s2.charCodeAt(i - k) - 97]--; // Remove left
if (arraysEqual(count, window)) return true;
}
return false;
}
function arraysEqual(a, b) {
return a.every((val, i) => val === b[i]);
}JavaScript implementation showing the numeric sum pattern and the character-count pattern for permutation checking. Uses fixed-size arrays for efficient character frequency tracking.
Pattern Variations
Maximum/Minimum Sum
O(n) / O(1)Find the k-length subarray with maximum or minimum sum. Track running sum and compare at each position.
Anagram/Permutation Detection
O(n) / O(k)Check if a window matches target character frequencies. Use frequency map or array comparison.
Sliding Window Maximum (Monotonic Deque)
O(n) / O(k)Find maximum in each k-window. Requires monotonic deque to maintain potential maximums in O(1) per step.
Distinct Count in Window
O(n) / O(k)Count distinct elements or check uniqueness within each k-window using hash set or map.
Practice Problems
| Problem | Difficulty | Type | Notes |
|---|---|---|---|
| Maximum Average Subarray I | easy | canonical | The classic fixed-window sum problem. Build first window, then slide. |
| Find All Anagrams in a String | medium | variant | Fixed window with character frequency matching. Common Meta/Google question. |
| Permutation in String | medium | variant | Same as anagrams but return boolean. Optimize with matches counter. |
| Maximum Points You Can Obtain from Cards | medium | variant | Trick: minimize middle window instead of maximizing ends. Common Google question. |
| Sliding Window Maximum | hard | follow-up | Requires monotonic deque to maintain window max in O(1). Classic hard problem. |
| Grumpy Bookstore Owner | medium | variant | Find best k-window to apply "secret technique". Two-phase calculation. |
| K Radius Subarray Averages | medium | variant | Compute average for every valid window. Handle edge indices. |
| Substring with Concatenation of All Words | hard | follow-up | Fixed window but with word-level (not character) matching. |
Interview Tips
- Immediately ask for k when you see "subarray of size..."—the fixed size is your signal
- Always build the first window separately before entering the slide loop
- Explain the O(n*k) to O(n) optimization—interviewers want to see you understand why
- For frequency problems, mention the int[26] array optimization over hash maps
- Edge case: check if k > array length before processing
Common Follow-up Questions
What if we need the actual subarray, not just the sum?
CommonTrack the starting index when you update max_sum. Store start_index = i - k + 1 whenever you find a new maximum. Return nums[start_index:start_index + k] at the end.
How would you find the maximum in each window instead of the sum?
CommonSum updates in O(1) but max doesn't—when you remove an element, it might have been the max. Use a monotonic decreasing deque: remove smaller elements from back when adding, remove front if it's outside window. Deque front is always current max. Still O(n) amortized.
What if negative numbers are allowed?
CommonFixed sliding window still works perfectly with negative numbers! The add/remove pattern is valid regardless of sign. It's variable sliding window for sum problems that breaks with negatives (because expanding doesn't always increase sum).
How would you handle this for a data stream (infinite input)?
Use a circular buffer of size k. Keep track of write position with modulo: pos = (pos + 1) % k. Maintain running sum. When buffer is full, subtract element being overwritten before adding new one.
Can you optimize space for the anagram problem?
CommonInstead of comparing two frequency arrays, use a "matches" counter. Start with matches = 0. Increment when a character count reaches target. Decrement when it leaves target. When matches == 26 (or alphabet size), you found an anagram. Single integer instead of array comparison.
Common Mistakes
Not building the first window separately
# WRONG: Starting slide at index 0
for i in range(len(nums)):
window_sum += nums[i]
if i >= k:
window_sum -= nums[i - k]
# No clear initial window, off-by-one likelyFix: Build the first window with sum(nums[:k]) or a separate loop for indices 0 to k-1. Then start your slide loop at index k. This makes the logic cleaner and avoids conditional checks inside the loop.
Off-by-one when removing the left element
# WRONG: Removing wrong element
for i in range(k, len(nums)):
window_sum += nums[i]
window_sum -= nums[i - k - 1] # Off by one!Fix: When adding nums[i], remove nums[i - k]. The window contains indices [i-k+1, i]. The element leaving is at index i - k (one position before the new window start).
Recalculating the entire window each iteration
# WRONG: O(n*k) complexity
for i in range(len(nums) - k + 1):
window_sum = sum(nums[i:i+k]) # Recalculating from scratch
max_sum = max(max_sum, window_sum)Fix: Use incremental updates: add the new element, remove the old one. This transforms O(n*k) into O(n). The whole point of sliding window is avoiding redundant computation.
Forgetting edge case when k > array length
# WRONG: Will crash or give wrong result
def max_average(nums, k):
window_sum = sum(nums[:k]) # IndexError if k > len(nums)
# ...Fix: Add an early return: if k > len(nums): return None (or handle per problem requirements). Some problems guarantee valid input, but always clarify with interviewer.
Frequently Asked Questions
What is the difference between fixed and variable sliding window?
Fixed sliding window has a constant window size k given in the problem. You always add one element and remove one element per step. Variable sliding window has a dynamic size determined by a condition (like "at most k distinct characters"). You expand the right side, then shrink from the left until valid. Fixed is simpler and always O(n); variable requires more careful tracking.
When should I use fixed sliding window vs. brute force?
Use fixed sliding window when: (1) you need to process all k-length subarrays, and (2) your aggregate function (sum, count, frequency) can be updated incrementally when one element enters and one leaves. If you can't update incrementally (e.g., finding median), you may need a different data structure or accept O(n*k).
How do I handle the frequency map comparison efficiently?
Option 1: Use a "matches" counter—increment when a char count reaches target, decrement when it leaves. Check if matches == alphabet_size. Option 2: Use a fixed int[26] array instead of hash map for lowercase letters. Option 3: Track "chars_to_match" count, decrementing when a char is fully matched.
Can fixed sliding window work on 2D arrays?
Yes, for fixed-size rectangular windows. Precompute prefix sums for the 2D array. Then any k×m rectangle sum can be computed in O(1) using inclusion-exclusion: sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]. Total time O(n*m) for all windows.
Why is Sliding Window Maximum harder than Sliding Window Sum?
Sum is "decomposable": new_sum = old_sum - removed + added. Max is not: when you remove the current maximum, you don't know the new max without scanning. The solution is a monotonic deque that maintains elements in decreasing order, discarding elements that can never be the maximum.
What's the relationship between sliding window and two pointers?
Sliding window is a specific application of two pointers where the pointers define window boundaries. In fixed sliding window, both pointers move together (right adds, left removes). In two pointers for sorted arrays, pointers move independently based on value comparison. Sliding window focuses on the content between pointers; classic two pointers focuses on elements at the pointers.