Sliding Window Technique - Learning Module

Loading content...

0/279

Fixed-Size Sliding Windows

The Straightforward Variant

Fixed-size sliding windows represent the most approachable form of the sliding window technique. The window size is given upfront—you don't need to decide how large it should be. Your job is simply to slide a window of exactly size k across the array, maintaining some aggregate state and extracting answers at each position.

This simplicity makes fixed-size windows an excellent starting point. Once you've internalized this pattern, the variable-size variant (where you must decide when to shrink) becomes a natural extension.

Characteristic Problems:

Find the maximum/minimum sum of any k consecutive elements
Find the average of each contiguous subarray of size k
Detect if any contiguous substring contains an anagram of a pattern
Find the maximum number of consecutive 1s if you can flip at most k 0s (fixed window of k operations)

What You Will Learn

By the end of this page, you will master the fixed-size sliding window template, understand the two-phase approach (build initial window, then slide), implement several classic problems efficiently, and develop reliable intuition for when fixed windows apply versus variable windows.

The Fixed-Size Sliding Window Template

The fixed-size sliding window follows a predictable two-phase structure:

Phase 1: Build the Initial Window Process the first k elements to establish your initial window state.

Phase 2: Slide the Window For each subsequent element, add it to the window and remove the element that falls out of the window (the element k positions behind).

Here's the complete, battle-tested template:

fixed_window_template.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def fixed_sliding_window(arr, k):
    """
    Fixed-size sliding window template.
    
    Time Complexity: O(n)
    Space Complexity: O(1) for simple aggregates, O(k) if storing window contents
    
    Args:
        arr: Input array
        k: Window size (must be <= len(arr))
    
    Returns:
        Results for each window position
    """
    n = len(arr)
    
    # Edge case: array smaller than window
    if n < k:
        return []  # or handle as appropriate
    
    # ========================================
    # PHASE 1: Build initial window [0, k-1]
    # ========================================
    # Initialize your state variable(s) here
    window_state = initial_value
    
    for i in range(k):
        # Add arr[i] to the window state
        update_state_on_entry(window_state, arr[i])
    
    # Record result for first window (if collecting all results)
    results = [extract_result(window_state)]
    
    # ========================================
    # PHASE 2: Slide window from position k to n-1
    # ========================================
    for i in range(k, n):
        # The element entering the window
        entering = arr[i]
        
        # The element leaving the window (k positions behind)
        leaving = arr[i - k]
        
        # Update state: add new element
        update_state_on_entry(window_state, entering)
        
        # Update state: remove old element
        update_state_on_exit(window_state, leaving)
        
        # Record result for this window position
        results.append(extract_result(window_state))
    
    return results

The Key Invariant

After processing index i (where i >= k-1), your window contains exactly elements arr[i-k+1] through arr[i]—that's k consecutive elements ending at index i. The result recorded is for this window. This invariant must hold throughout the sliding phase.

Why Two Phases?

You might wonder why we don't just iterate from 0 to n-1 with conditional logic. The two-phase approach is cleaner because:

No conditionals in the main loop — The sliding phase has uniform logic for every iteration
Clearer reasoning — Phase 1 builds, Phase 2 slides; no mixing of concerns
Fewer edge case bugs — You explicitly handle the initial window, rather than embedding special cases in a single loop

However, some implementations combine both phases with conditional checks. Both work; the two-phase approach tends to be more readable and less error-prone.

Example: Maximum Sum of K Consecutive Elements

Let's apply the template to the classic problem: find the maximum sum of any k consecutive elements in an array.

Problem Statement: Given an array of integers arr and an integer k, find the maximum sum of any contiguous subarray of exactly k elements.

Example:

Input:  arr = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray [5, 1, 3] has the maximum sum = 9

max_sum_subarray_k.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def max_sum_subarray_k(arr, k):
    """
    Find maximum sum of any k consecutive elements.
    
    Time: O(n), Space: O(1)
    """
    n = len(arr)
    
    if n < k:
        return None  # Not enough elements
    
    # Phase 1: Build initial window sum
    window_sum = 0
    for i in range(k):
        window_sum += arr[i]
    
    max_sum = window_sum  # First window is the best so far
    
    # Phase 2: Slide the window
    for i in range(k, n):
        # Slide: add new element, remove old element
        window_sum += arr[i]         # entering element
        window_sum -= arr[i - k]     # leaving element
        
        # Update maximum
        max_sum = max(max_sum, window_sum)
    
    return max_sum
 
 
# Trace through example: arr = [2, 1, 5, 1, 3, 2], k = 3
# 
# Phase 1 (indices 0, 1, 2):
#   window_sum = 2 + 1 + 5 = 8
#   max_sum = 8
#   Window: [2, 1, 5]
#
# Phase 2:
#   i = 3: entering = arr[3] = 1, leaving = arr[0] = 2
#          window_sum = 8 + 1 - 2 = 7
#          max_sum = max(8, 7) = 8
#          Window: [1, 5, 1]
#
#   i = 4: entering = arr[4] = 3, leaving = arr[1] = 1
#          window_sum = 7 + 3 - 1 = 9
#          max_sum = max(8, 9) = 9
#          Window: [5, 1, 3]
#
#   i = 5: entering = arr[5] = 2, leaving = arr[2] = 5
#          window_sum = 9 + 2 - 5 = 6
#          max_sum = max(9, 6) = 9
#          Window: [1, 3, 2]
#
# Result: 9

Why This Works

Each element is added exactly once (when it enters the window) and removed exactly once (when it leaves). Total operations: n additions and n-k removals for the sliding phase, plus k additions for the initial window. Total: 2n - k + k = 2n operations, which is O(n).

Example: Average of All Contiguous Subarrays

Another common application: compute the average of every contiguous subarray of size k. This is foundational for time-series analysis and moving average calculations.

Problem Statement: Given an array arr and window size k, return an array of averages where each element is the average of k consecutive elements starting at that position.

Example:

Input:  arr = [1, 3, 2, 6, -1, 4, 1, 8, 2], k = 5
Output: [2.2, 2.8, 2.4, 3.6, 2.8]

Explanation:
  [1, 3, 2, 6, -1] → avg = 11/5 = 2.2
  [3, 2, 6, -1, 4] → avg = 14/5 = 2.8
  [2, 6, -1, 4, 1] → avg = 12/5 = 2.4
  [6, -1, 4, 1, 8] → avg = 18/5 = 3.6
  [-1, 4, 1, 8, 2] → avg = 14/5 = 2.8

moving_average.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def find_averages_of_subarrays(arr, k):
    """
    Find the average of every contiguous subarray of size k.
    
    Time: O(n), Space: O(n-k+1) for output
    """
    n = len(arr)
    result = []
    
    if n < k:
        return result
    
    # Phase 1: Build initial window
    window_sum = 0.0
    for i in range(k):
        window_sum += arr[i]
    
    result.append(window_sum / k)
    
    # Phase 2: Slide
    for i in range(k, n):
        window_sum += arr[i]        # Add entering element
        window_sum -= arr[i - k]    # Remove leaving element
        result.append(window_sum / k)
    
    return result
 
 
# Alternative: Single-loop version with conditional
def find_averages_single_loop(arr, k):
    """
    Same result, single loop with conditional.
    Some prefer this; others find two-phase clearer.
    """
    n = len(arr)
    result = []
    window_sum = 0.0
    
    for i in range(n):
        window_sum += arr[i]  # Always add current element
        
        if i >= k:
            window_sum -= arr[i - k]  # Remove element fallen out
        
        if i >= k - 1:
            result.append(window_sum / k)  # Window is complete
    
    return result

Practical Applications:

Moving averages are ubiquitous in:

Financial analysis — 50-day and 200-day moving averages for stock prices
Signal processing — Smoothing noisy sensor data
System monitoring — Tracking rolling averages of CPU usage, request latency, etc.
Sports analytics — Rolling batting averages, points per game

The O(n) sliding window approach is essential when processing streaming data or massive datasets where recomputing from scratch isn't feasible.

Example: Finding Anagrams in a String

Not all sliding window problems involve numeric sums. Let's tackle a string problem: find all starting indices where an anagram of a pattern string appears in a larger string.

Problem Statement: Given a string s and a pattern p, find all starting indices of p's anagrams in s.

Two strings are anagrams if they contain the same characters with the same frequencies.

Example:

Input:  s = "cbaebabacd", p = "abc"
Output: [0, 6]

Explanation:
  s[0:3] = "cba" → anagram of "abc" ✓
  s[6:9] = "bac" → anagram of "abc" ✓

Key Insight: Since anagrams have the same length as the pattern, we use a fixed window of size len(p). Instead of tracking a sum, we track character frequencies.

find_anagrams.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
from collections import defaultdict
 
def find_anagrams(s, p):
    """
    Find all start indices of p's anagrams in s.
    
    Time: O(n), where n = len(s)
    Space: O(1), since we track at most 26 characters
    
    Strategy:
    - Track frequency of each char in current window
    - Track frequency of each char in pattern
    - Compare: if they match, it's an anagram
    """
    result = []
    len_s, len_p = len(s), len(p)
    
    if len_s < len_p:
        return result
    
    # Frequency maps
    p_freq = defaultdict(int)
    window_freq = defaultdict(int)
    
    # Build pattern frequency map
    for char in p:
        p_freq[char] += 1
    
    # Phase 1: Build initial window of size len_p
    for i in range(len_p):
        window_freq[s[i]] += 1
    
    # Check if initial window is an anagram
    if window_freq == p_freq:
        result.append(0)
    
    # Phase 2: Slide the window
    for i in range(len_p, len_s):
        # Add entering character
        entering = s[i]
        window_freq[entering] += 1
        
        # Remove leaving character
        leaving = s[i - len_p]
        window_freq[leaving] -= 1
        if window_freq[leaving] == 0:
            del window_freq[leaving]  # Keep map clean
        
        # Check if current window is an anagram
        if window_freq == p_freq:
            result.append(i - len_p + 1)  # Start index of this window
    
    return result
 
 
# Trace: s = "cbaebabacd", p = "abc"
# p_freq = {'a': 1, 'b': 1, 'c': 1}
# 
# Phase 1 (i=0,1,2): window = "cba"
#   window_freq = {'c': 1, 'b': 1, 'a': 1}
#   Match! result = [0]
#
# Phase 2:
#   i=3: enter 'e', leave 'c'
#        window_freq = {'b': 1, 'a': 1, 'e': 1}
#        No match
#
#   i=4: enter 'b', leave 'b'
#        window_freq = {'b': 1, 'a': 1, 'e': 1}
#        No match
#
#   ... (continuing)
#
#   i=8: enter 'c', leave 'b'
#        window = "bac"
#        window_freq = {'b': 1, 'a': 1, 'c': 1}
#        Match! result = [0, 6]

Optimization: Counting Matches

Comparing two dictionaries takes O(26) = O(1) for lowercase letters, but we can do better. Track a 'matches' counter: how many characters have the correct frequency. When matches equals the number of distinct characters in p, we have an anagram. This avoids dictionary comparison entirely.

find_anagrams_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def find_anagrams_optimized(s, p):
    """
    Optimized version using a match counter.
    
    Instead of comparing entire frequency maps,
    track how many characters have matching counts.
    """
    result = []
    len_s, len_p = len(s), len(p)
    
    if len_s < len_p:
        return result
    
    # Frequency arrays (for lowercase letters)
    p_freq = [0] * 26
    window_freq = [0] * 26
    
    def char_index(c):
        return ord(c) - ord('a')
    
    # Build pattern frequency
    for char in p:
        p_freq[char_index(char)] += 1
    
    # Track matches: count of characters with matching frequency
    matches = 0
    required = sum(1 for f in p_freq if f > 0)  # Distinct chars in p
    
    for i in range(len_s):
        # Add entering character
        idx = char_index(s[i])
        window_freq[idx] += 1
        
        # Update matches for entering character
        if window_freq[idx] == p_freq[idx]:
            matches += 1
        elif window_freq[idx] == p_freq[idx] + 1:
            matches -= 1  # Was matching, now exceeds
        
        # Remove leaving character (if window exceeds size)
        if i >= len_p:
            leaving_idx = char_index(s[i - len_p])
            
            if window_freq[leaving_idx] == p_freq[leaving_idx]:
                matches -= 1  # Was matching, will stop
            elif window_freq[leaving_idx] == p_freq[leaving_idx] + 1:
                matches += 1  # Will become matching
            
            window_freq[leaving_idx] -= 1
        
        # Check for anagram (window complete and all matches)
        if i >= len_p - 1 and matches == required:
            result.append(i - len_p + 1)
    
    return result

Example: Maximum in Each Sliding Window

Here's a more challenging fixed-window problem: find the maximum value in each window of size k. This reveals an important limitation: not all aggregates can be maintained in O(1) per slide with simple state.

Problem Statement: Given an array arr and window size k, return an array of maximums where each element is the maximum of k consecutive elements.

The Challenge: Unlike sum, you cannot compute the new maximum by subtracting the leaving element. If the leaving element WAS the maximum, you must scan the remaining k-1 elements to find the new max—that's O(k) per slide, giving O(nk) overall.

The Solution: Monotonic Deque Use a deque (double-ended queue) that maintains indices of potential maximum candidates in decreasing order of their values. This enables O(1) amortized update per element.

max_sliding_window.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from collections import deque
 
def max_sliding_window(arr, k):
    """
    Find maximum in each sliding window of size k.
    
    Time: O(n) - each element enters and exits deque at most once
    Space: O(k) - deque stores at most k indices
    
    The deque stores INDICES (not values) of potential maximums.
    Invariant: values at deque indices are in strictly decreasing order.
    """
    n = len(arr)
    result = []
    dq = deque()  # Stores indices
    
    for i in range(n):
        # Step 1: Remove indices outside current window
        # The front of deque should be within [i-k+1, i]
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Step 2: Remove indices whose values are <= current value
        # They can never be the maximum while current element is in window
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()
        
        # Step 3: Add current index
        dq.append(i)
        
        # Step 4: Record maximum for complete windows
        if i >= k - 1:
            # Front of deque is always the maximum for current window
            result.append(arr[dq[0]])
    
    return result
 
 
# Visual trace: arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
#
# i=0 (val=1):
#   dq = [0]
#   Window incomplete
#
# i=1 (val=3):
#   Remove indices with value <= 3: remove 0 (arr[0]=1 < 3)
#   dq = [1]
#   Window incomplete
#
# i=2 (val=-1):
#   dq = [1, 2]
#   Window complete: [1, 3, -1], max = arr[1] = 3
#   result = [3]
#
# i=3 (val=-3):
#   dq = [1, 2, 3]
#   Index 1 still in window [1, 3]? Yes (i-k+1 = 1)
#   Window: [3, -1, -3], max = arr[1] = 3
#   result = [3, 3]
#
# i=4 (val=5):
#   Index 1 out of window now (i-k+1 = 2 > 1): remove 1
#   Remove indices with value <= 5: remove all
#   dq = [4]
#   Window: [-1, -3, 5], max = arr[4] = 5
#   result = [3, 3, 5]
#
# i=5 (val=3):
#   dq = [4, 5]
#   Window: [-3, 5, 3], max = arr[4] = 5
#   result = [3, 3, 5, 5]
#
# i=6 (val=6):
#   Remove indices with value <= 6: remove 4, 5
#   dq = [6]
#   Window: [5, 3, 6], max = arr[6] = 6
#   result = [3, 3, 5, 5, 6]
#
# i=7 (val=7):
#   Remove 6 (arr[6]=6 < 7)
#   dq = [7]
#   Window: [3, 6, 7], max = arr[7] = 7
#   result = [3, 3, 5, 5, 6, 7]

Why O(n) Despite Nested Loops?

The code has while loops inside a for loop, which might suggest O(n²). But analyze what happens to each element: it enters the deque exactly once and exits at most once. Total operations across all iterations: at most 2n. This is amortized O(n), a powerful technique you'll see in many advanced algorithms.

Common Patterns and Variations

Fixed-size sliding windows appear in many variations. Here are patterns you'll encounter:

Fixed-Size Sliding Window Variations
Problem Type	State to Track	Key Technique
Max/Min sum of k elements	Running sum	Add entering, subtract leaving
Average of k elements	Running sum	Divide by k for average
Product of k elements	Running product	Multiply/divide (handle zeros specially)
Max/Min in each window	Monotonic deque	Amortized O(1) per element
Contains duplicate in k range	Hash set of window	Add/remove from set
Distinct elements count	Hash map + distinct counter	Track frequency, update counter on 0↔1
Anagram/permutation match	Frequency map/array	Compare with target frequency
Fixed-width range query	Segment tree or BIT	O(log n) per query if needed

Choosing the Right State Structure:

The key to efficient fixed-window solutions is choosing a state that supports O(1) or O(log n) updates:

Simple aggregates (sum, count): Plain variables, O(1) update
Frequency tracking: Hash map or fixed-size array, O(1) update
Order statistics (max, min, median): Specialized structures
- Monotonic deque for max/min: O(1) amortized
- Two heaps for median: O(log k) per update
- Balanced BST for any order statistic: O(log k) per update

If no efficient update exists for your aggregate, sliding window may not provide asymptotic improvement over brute force—though it might still simplify the code.

Edge Cases and Robustness

Production-quality sliding window code must handle edge cases gracefully:

Edge Cases to Handle

•Empty array — n = 0. Return empty result or handle as error.
•Array smaller than window — n < k. No valid windows exist. Decide: return empty, raise error, or return partial?
•Window size 0 — k = 0. Usually invalid; handle explicitly.
•Window size 1 — k = 1. Degenerate case: each element is its own window. Algorithm should work, but verify.
•Window size equals array length — k = n. Exactly one window: the entire array.
•Negative numbers — If assuming non-negative, negatives can break logic (e.g., product tracking).
•Zeros in product windows — Division by zero when departing element is zero. Track zero count separately.
•Integer overflow — Large sums or products can overflow. Use appropriate numeric types.

robust_sliding_window.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def max_sum_subarray_robust(arr, k):
    """
    Production-quality implementation with edge case handling.
    """
    # Input validation
    if arr is None:
        raise ValueError("Input array cannot be None")
    
    n = len(arr)
    
    if k <= 0:
        raise ValueError(f"Window size must be positive, got {k}")
    
    if n == 0:
        return None  # Or raise, depending on requirements
    
    if k > n:
        # Option 1: Return None/error
        return None
        # Option 2: Return max of entire array
        # return max(arr)
        # Option 3: Treat as if k = n
        # k = n
    
    # Main algorithm (after validation)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Document Your Assumptions

In interviews, explicitly state: 'I'm assuming k <= n and k > 0. If these don't hold, I'd add validation here.' This shows awareness without spending time on edge cases when the interviewer wants to see the core algorithm.

Summary: Fixed-Size Sliding Windows Mastered

You've now mastered fixed-size sliding windows. Let's consolidate:

Key Takeaways

•Two-phase structure: Build initial window (first k elements), then slide (add entering, remove leaving).
•State must support efficient update: Sum, count, frequency map work in O(1). Max/min need monotonic deque for O(1) amortized.
•O(n) complexity: Each element enters once and leaves once. Total work is linear regardless of window size.
•The template is reusable: The structure stays the same; you customize what state to track and what to extract.
•Handle edge cases: Empty arrays, k > n, k = 0, and numeric edge cases must be considered.
•Monotonic deque unlocks order statistics: When simple aggregates don't suffice, specialized data structures extend sliding window's power.

What's Next:

Fixed-size windows are straightforward because the window size is given. Variable-size sliding windows add a layer of complexity: you must decide when to shrink the window. The next page teaches you to handle this elegantly, expanding your toolkit to problems like "longest substring with at most k distinct characters" and "smallest subarray with sum ≥ target."

Fixed Windows Conquered

You can now confidently apply fixed-size sliding windows to a wide range of problems. You understand the template, can choose appropriate state structures, and know when specialized structures like monotonic deques are needed. Next: variable-size windows, where the challenge shifts from 'what' to track to 'when' to shrink.

Fixed-Size Sliding Windows

The Straightforward Variant

Characteristic Problems:

Find the maximum/minimum sum of any k consecutive elements
Find the average of each contiguous subarray of size k
Detect if any contiguous substring contains an anagram of a pattern
Find the maximum number of consecutive 1s if you can flip at most k 0s (fixed window of k operations)

What You Will Learn

The Fixed-Size Sliding Window Template

The fixed-size sliding window follows a predictable two-phase structure:

Phase 1: Build the Initial Window Process the first k elements to establish your initial window state.

Phase 2: Slide the Window For each subsequent element, add it to the window and remove the element that falls out of the window (the element k positions behind).

Here's the complete, battle-tested template:

fixed_window_template.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def fixed_sliding_window(arr, k):
    """
    Fixed-size sliding window template.
    
    Time Complexity: O(n)
    Space Complexity: O(1) for simple aggregates, O(k) if storing window contents
    
    Args:
        arr: Input array
        k: Window size (must be <= len(arr))
    
    Returns:
        Results for each window position
    """
    n = len(arr)
    
    # Edge case: array smaller than window
    if n < k:
        return []  # or handle as appropriate
    
    # ========================================
    # PHASE 1: Build initial window [0, k-1]
    # ========================================
    # Initialize your state variable(s) here
    window_state = initial_value
    
    for i in range(k):
        # Add arr[i] to the window state
        update_state_on_entry(window_state, arr[i])
    
    # Record result for first window (if collecting all results)
    results = [extract_result(window_state)]
    
    # ========================================
    # PHASE 2: Slide window from position k to n-1
    # ========================================
    for i in range(k, n):
        # The element entering the window
        entering = arr[i]
        
        # The element leaving the window (k positions behind)
        leaving = arr[i - k]
        
        # Update state: add new element
        update_state_on_entry(window_state, entering)
        
        # Update state: remove old element
        update_state_on_exit(window_state, leaving)
        
        # Record result for this window position
        results.append(extract_result(window_state))
    
    return results

The Key Invariant

Why Two Phases?

You might wonder why we don't just iterate from 0 to n-1 with conditional logic. The two-phase approach is cleaner because:

No conditionals in the main loop — The sliding phase has uniform logic for every iteration
Clearer reasoning — Phase 1 builds, Phase 2 slides; no mixing of concerns
Fewer edge case bugs — You explicitly handle the initial window, rather than embedding special cases in a single loop

However, some implementations combine both phases with conditional checks. Both work; the two-phase approach tends to be more readable and less error-prone.

Example: Maximum Sum of K Consecutive Elements

Let's apply the template to the classic problem: find the maximum sum of any k consecutive elements in an array.

Problem Statement: Given an array of integers arr and an integer k, find the maximum sum of any contiguous subarray of exactly k elements.

Example:

Input:  arr = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray [5, 1, 3] has the maximum sum = 9

max_sum_subarray_k.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def max_sum_subarray_k(arr, k):
    """
    Find maximum sum of any k consecutive elements.
    
    Time: O(n), Space: O(1)
    """
    n = len(arr)
    
    if n < k:
        return None  # Not enough elements
    
    # Phase 1: Build initial window sum
    window_sum = 0
    for i in range(k):
        window_sum += arr[i]
    
    max_sum = window_sum  # First window is the best so far
    
    # Phase 2: Slide the window
    for i in range(k, n):
        # Slide: add new element, remove old element
        window_sum += arr[i]         # entering element
        window_sum -= arr[i - k]     # leaving element
        
        # Update maximum
        max_sum = max(max_sum, window_sum)
    
    return max_sum
 
 
# Trace through example: arr = [2, 1, 5, 1, 3, 2], k = 3
# 
# Phase 1 (indices 0, 1, 2):
#   window_sum = 2 + 1 + 5 = 8
#   max_sum = 8
#   Window: [2, 1, 5]
#
# Phase 2:
#   i = 3: entering = arr[3] = 1, leaving = arr[0] = 2
#          window_sum = 8 + 1 - 2 = 7
#          max_sum = max(8, 7) = 8
#          Window: [1, 5, 1]
#
#   i = 4: entering = arr[4] = 3, leaving = arr[1] = 1
#          window_sum = 7 + 3 - 1 = 9
#          max_sum = max(8, 9) = 9
#          Window: [5, 1, 3]
#
#   i = 5: entering = arr[5] = 2, leaving = arr[2] = 5
#          window_sum = 9 + 2 - 5 = 6
#          max_sum = max(9, 6) = 9
#          Window: [1, 3, 2]
#
# Result: 9

Why This Works

Example: Average of All Contiguous Subarrays

Another common application: compute the average of every contiguous subarray of size k. This is foundational for time-series analysis and moving average calculations.

Problem Statement: Given an array arr and window size k, return an array of averages where each element is the average of k consecutive elements starting at that position.

Example:

Input:  arr = [1, 3, 2, 6, -1, 4, 1, 8, 2], k = 5
Output: [2.2, 2.8, 2.4, 3.6, 2.8]

Explanation:
  [1, 3, 2, 6, -1] → avg = 11/5 = 2.2
  [3, 2, 6, -1, 4] → avg = 14/5 = 2.8
  [2, 6, -1, 4, 1] → avg = 12/5 = 2.4
  [6, -1, 4, 1, 8] → avg = 18/5 = 3.6
  [-1, 4, 1, 8, 2] → avg = 14/5 = 2.8

moving_average.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def find_averages_of_subarrays(arr, k):
    """
    Find the average of every contiguous subarray of size k.
    
    Time: O(n), Space: O(n-k+1) for output
    """
    n = len(arr)
    result = []
    
    if n < k:
        return result
    
    # Phase 1: Build initial window
    window_sum = 0.0
    for i in range(k):
        window_sum += arr[i]
    
    result.append(window_sum / k)
    
    # Phase 2: Slide
    for i in range(k, n):
        window_sum += arr[i]        # Add entering element
        window_sum -= arr[i - k]    # Remove leaving element
        result.append(window_sum / k)
    
    return result
 
 
# Alternative: Single-loop version with conditional
def find_averages_single_loop(arr, k):
    """
    Same result, single loop with conditional.
    Some prefer this; others find two-phase clearer.
    """
    n = len(arr)
    result = []
    window_sum = 0.0
    
    for i in range(n):
        window_sum += arr[i]  # Always add current element
        
        if i >= k:
            window_sum -= arr[i - k]  # Remove element fallen out
        
        if i >= k - 1:
            result.append(window_sum / k)  # Window is complete
    
    return result

Practical Applications:

Moving averages are ubiquitous in:

Financial analysis — 50-day and 200-day moving averages for stock prices
Signal processing — Smoothing noisy sensor data
System monitoring — Tracking rolling averages of CPU usage, request latency, etc.
Sports analytics — Rolling batting averages, points per game

The O(n) sliding window approach is essential when processing streaming data or massive datasets where recomputing from scratch isn't feasible.

Example: Finding Anagrams in a String

Not all sliding window problems involve numeric sums. Let's tackle a string problem: find all starting indices where an anagram of a pattern string appears in a larger string.

Problem Statement: Given a string s and a pattern p, find all starting indices of p's anagrams in s.

Two strings are anagrams if they contain the same characters with the same frequencies.

Example:

Input:  s = "cbaebabacd", p = "abc"
Output: [0, 6]

Explanation:
  s[0:3] = "cba" → anagram of "abc" ✓
  s[6:9] = "bac" → anagram of "abc" ✓

Key Insight: Since anagrams have the same length as the pattern, we use a fixed window of size len(p). Instead of tracking a sum, we track character frequencies.

find_anagrams.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
from collections import defaultdict
 
def find_anagrams(s, p):
    """
    Find all start indices of p's anagrams in s.
    
    Time: O(n), where n = len(s)
    Space: O(1), since we track at most 26 characters
    
    Strategy:
    - Track frequency of each char in current window
    - Track frequency of each char in pattern
    - Compare: if they match, it's an anagram
    """
    result = []
    len_s, len_p = len(s), len(p)
    
    if len_s < len_p:
        return result
    
    # Frequency maps
    p_freq = defaultdict(int)
    window_freq = defaultdict(int)
    
    # Build pattern frequency map
    for char in p:
        p_freq[char] += 1
    
    # Phase 1: Build initial window of size len_p
    for i in range(len_p):
        window_freq[s[i]] += 1
    
    # Check if initial window is an anagram
    if window_freq == p_freq:
        result.append(0)
    
    # Phase 2: Slide the window
    for i in range(len_p, len_s):
        # Add entering character
        entering = s[i]
        window_freq[entering] += 1
        
        # Remove leaving character
        leaving = s[i - len_p]
        window_freq[leaving] -= 1
        if window_freq[leaving] == 0:
            del window_freq[leaving]  # Keep map clean
        
        # Check if current window is an anagram
        if window_freq == p_freq:
            result.append(i - len_p + 1)  # Start index of this window
    
    return result
 
 
# Trace: s = "cbaebabacd", p = "abc"
# p_freq = {'a': 1, 'b': 1, 'c': 1}
# 
# Phase 1 (i=0,1,2): window = "cba"
#   window_freq = {'c': 1, 'b': 1, 'a': 1}
#   Match! result = [0]
#
# Phase 2:
#   i=3: enter 'e', leave 'c'
#        window_freq = {'b': 1, 'a': 1, 'e': 1}
#        No match
#
#   i=4: enter 'b', leave 'b'
#        window_freq = {'b': 1, 'a': 1, 'e': 1}
#        No match
#
#   ... (continuing)
#
#   i=8: enter 'c', leave 'b'
#        window = "bac"
#        window_freq = {'b': 1, 'a': 1, 'c': 1}
#        Match! result = [0, 6]

Optimization: Counting Matches

find_anagrams_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def find_anagrams_optimized(s, p):
    """
    Optimized version using a match counter.
    
    Instead of comparing entire frequency maps,
    track how many characters have matching counts.
    """
    result = []
    len_s, len_p = len(s), len(p)
    
    if len_s < len_p:
        return result
    
    # Frequency arrays (for lowercase letters)
    p_freq = [0] * 26
    window_freq = [0] * 26
    
    def char_index(c):
        return ord(c) - ord('a')
    
    # Build pattern frequency
    for char in p:
        p_freq[char_index(char)] += 1
    
    # Track matches: count of characters with matching frequency
    matches = 0
    required = sum(1 for f in p_freq if f > 0)  # Distinct chars in p
    
    for i in range(len_s):
        # Add entering character
        idx = char_index(s[i])
        window_freq[idx] += 1
        
        # Update matches for entering character
        if window_freq[idx] == p_freq[idx]:
            matches += 1
        elif window_freq[idx] == p_freq[idx] + 1:
            matches -= 1  # Was matching, now exceeds
        
        # Remove leaving character (if window exceeds size)
        if i >= len_p:
            leaving_idx = char_index(s[i - len_p])
            
            if window_freq[leaving_idx] == p_freq[leaving_idx]:
                matches -= 1  # Was matching, will stop
            elif window_freq[leaving_idx] == p_freq[leaving_idx] + 1:
                matches += 1  # Will become matching
            
            window_freq[leaving_idx] -= 1
        
        # Check for anagram (window complete and all matches)
        if i >= len_p - 1 and matches == required:
            result.append(i - len_p + 1)
    
    return result

Example: Maximum in Each Sliding Window

Problem Statement: Given an array arr and window size k, return an array of maximums where each element is the maximum of k consecutive elements.

max_sliding_window.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from collections import deque
 
def max_sliding_window(arr, k):
    """
    Find maximum in each sliding window of size k.
    
    Time: O(n) - each element enters and exits deque at most once
    Space: O(k) - deque stores at most k indices
    
    The deque stores INDICES (not values) of potential maximums.
    Invariant: values at deque indices are in strictly decreasing order.
    """
    n = len(arr)
    result = []
    dq = deque()  # Stores indices
    
    for i in range(n):
        # Step 1: Remove indices outside current window
        # The front of deque should be within [i-k+1, i]
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Step 2: Remove indices whose values are <= current value
        # They can never be the maximum while current element is in window
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()
        
        # Step 3: Add current index
        dq.append(i)
        
        # Step 4: Record maximum for complete windows
        if i >= k - 1:
            # Front of deque is always the maximum for current window
            result.append(arr[dq[0]])
    
    return result
 
 
# Visual trace: arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
#
# i=0 (val=1):
#   dq = [0]
#   Window incomplete
#
# i=1 (val=3):
#   Remove indices with value <= 3: remove 0 (arr[0]=1 < 3)
#   dq = [1]
#   Window incomplete
#
# i=2 (val=-1):
#   dq = [1, 2]
#   Window complete: [1, 3, -1], max = arr[1] = 3
#   result = [3]
#
# i=3 (val=-3):
#   dq = [1, 2, 3]
#   Index 1 still in window [1, 3]? Yes (i-k+1 = 1)
#   Window: [3, -1, -3], max = arr[1] = 3
#   result = [3, 3]
#
# i=4 (val=5):
#   Index 1 out of window now (i-k+1 = 2 > 1): remove 1
#   Remove indices with value <= 5: remove all
#   dq = [4]
#   Window: [-1, -3, 5], max = arr[4] = 5
#   result = [3, 3, 5]
#
# i=5 (val=3):
#   dq = [4, 5]
#   Window: [-3, 5, 3], max = arr[4] = 5
#   result = [3, 3, 5, 5]
#
# i=6 (val=6):
#   Remove indices with value <= 6: remove 4, 5
#   dq = [6]
#   Window: [5, 3, 6], max = arr[6] = 6
#   result = [3, 3, 5, 5, 6]
#
# i=7 (val=7):
#   Remove 6 (arr[6]=6 < 7)
#   dq = [7]
#   Window: [3, 6, 7], max = arr[7] = 7
#   result = [3, 3, 5, 5, 6, 7]

Why O(n) Despite Nested Loops?

Common Patterns and Variations

Fixed-size sliding windows appear in many variations. Here are patterns you'll encounter:

Fixed-Size Sliding Window Variations
Problem Type	State to Track	Key Technique
Max/Min sum of k elements	Running sum	Add entering, subtract leaving
Average of k elements	Running sum	Divide by k for average
Product of k elements	Running product	Multiply/divide (handle zeros specially)
Max/Min in each window	Monotonic deque	Amortized O(1) per element
Contains duplicate in k range	Hash set of window	Add/remove from set
Distinct elements count	Hash map + distinct counter	Track frequency, update counter on 0↔1
Anagram/permutation match	Frequency map/array	Compare with target frequency
Fixed-width range query	Segment tree or BIT	O(log n) per query if needed

Choosing the Right State Structure:

The key to efficient fixed-window solutions is choosing a state that supports O(1) or O(log n) updates:

Simple aggregates (sum, count): Plain variables, O(1) update
Frequency tracking: Hash map or fixed-size array, O(1) update
Order statistics (max, min, median): Specialized structures
- Monotonic deque for max/min: O(1) amortized
- Two heaps for median: O(log k) per update
- Balanced BST for any order statistic: O(log k) per update

If no efficient update exists for your aggregate, sliding window may not provide asymptotic improvement over brute force—though it might still simplify the code.

Edge Cases and Robustness

Production-quality sliding window code must handle edge cases gracefully:

Edge Cases to Handle

•Empty array — n = 0. Return empty result or handle as error.
•Array smaller than window — n < k. No valid windows exist. Decide: return empty, raise error, or return partial?
•Window size 0 — k = 0. Usually invalid; handle explicitly.
•Window size 1 — k = 1. Degenerate case: each element is its own window. Algorithm should work, but verify.
•Window size equals array length — k = n. Exactly one window: the entire array.
•Negative numbers — If assuming non-negative, negatives can break logic (e.g., product tracking).
•Zeros in product windows — Division by zero when departing element is zero. Track zero count separately.
•Integer overflow — Large sums or products can overflow. Use appropriate numeric types.

robust_sliding_window.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def max_sum_subarray_robust(arr, k):
    """
    Production-quality implementation with edge case handling.
    """
    # Input validation
    if arr is None:
        raise ValueError("Input array cannot be None")
    
    n = len(arr)
    
    if k <= 0:
        raise ValueError(f"Window size must be positive, got {k}")
    
    if n == 0:
        return None  # Or raise, depending on requirements
    
    if k > n:
        # Option 1: Return None/error
        return None
        # Option 2: Return max of entire array
        # return max(arr)
        # Option 3: Treat as if k = n
        # k = n
    
    # Main algorithm (after validation)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Document Your Assumptions

Summary: Fixed-Size Sliding Windows Mastered

You've now mastered fixed-size sliding windows. Let's consolidate:

Key Takeaways

•Two-phase structure: Build initial window (first k elements), then slide (add entering, remove leaving).
•State must support efficient update: Sum, count, frequency map work in O(1). Max/min need monotonic deque for O(1) amortized.
•O(n) complexity: Each element enters once and leaves once. Total work is linear regardless of window size.
•The template is reusable: The structure stays the same; you customize what state to track and what to extract.
•Handle edge cases: Empty arrays, k > n, k = 0, and numeric edge cases must be considered.
•Monotonic deque unlocks order statistics: When simple aggregates don't suffice, specialized data structures extend sliding window's power.

What's Next:

Fixed Windows Conquered