Skip to main content

Sliding Window

TL;DR​

Sliding window maintains a contiguous subset of elements (window) and efficiently processes it. Fixed-size windows process all windows of specific size k. Variable-size windows expand/contract based on validity conditions. Two pointers (left/right) mark window boundaries. Remove elements as left pointer advances, add elements as right pointer advances. This transforms O(n²) nested loops into O(n) or O(n + m) complexity.

Core Concepts​

Fixed Size Window​

Approach: Maintain window of exactly k elements. Slide by removing leftmost, adding next element.

Pattern:

  1. Initialize window with first k elements
  2. Calculate result for current window
  3. Slide: remove element at index i-k, add element at index i
  4. Repeat until right pointer reaches end

Time complexity: O(n) - each element added and removed once

Applications:

  • Maximum/minimum in each window
  • Average of each k-sized window
  • Distinct elements in each window

Variable Size Window​

Approach: Expand right boundary until condition met, contract left boundary when needed.

Pattern:

  1. Expand right pointer, adding new elements
  2. While condition invalid, contract from left
  3. When valid, update result
  4. Continue until right pointer reaches end

Time complexity: O(n) - each element added and removed once, despite nested while loops

Applications:

  • Longest substring with condition
  • Shortest substring with condition
  • Subarray sum problems

Window Contraction and Expansion​

Expand: Move right pointer to include more elements. Increases window size and adds new element's contribution.

Contract: Move left pointer to exclude elements. Decreases window size and removes left element's contribution.

Key insight: Each element is visited at most twice (once by right pointer, once by left pointer), giving O(n) total despite appearing like nested loops.

Maintaining Window State​

Character frequency: Hash map tracking character counts in current window Sum: Maintain running sum, add right element, subtract left element Unique count: Counter of unique elements, increment when first occurrence, decrement when last removed Distinct elements: Set or frequency map of unique elements in window

Update state incrementally as boundaries change rather than recalculating from scratch.

Key Algorithms and Techniques​

Fixed Window Maximum​

Deque-based approach: maintain indices of elements in decreasing order. Remove front when outside window, remove back for smaller elements.

Variable Window Longest Substring​

Hash map for character frequencies. Expand right, contract left when duplicates exist.

Minimum Window Substring​

Two hash maps: one for target characters, one for window characters. Match count tracks how many unique characters have required frequency.

Maximum Subarray Sum of Size K​

Track running sum. Slide window, update max. O(n) time, O(1) space.

Practical Example​

# Fixed window: maximum sum of k consecutive elements
def max_sum_k(arr, k):
    if k > len(arr):
        return 0
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    return max_sum

# Variable window: longest substring without repeating characters
def longest_substring_without_repeating(s):
    char_index = {}
    max_length = 0
    left = 0
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)
    return max_length

# Variable window: minimum window substring
def min_window_substring(s, t):
    if len(t) > len(s):
        return ""
    target_count = {}
    for char in t:
        target_count[char] = target_count.get(char, 0) + 1

    required = len(target_count)
    window_count = {}
    formed = 0
    left, right = 0, 0
    min_len = float('inf')
    min_start = 0

    while right < len(s):
        char = s[right]
        window_count[char] = window_count.get(char, 0) + 1
        if char in target_count and window_count[char] == target_count[char]:
            formed += 1

        while left <= right and formed == required:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left
            char = s[left]
            window_count[char] -= 1
            if char in target_count and window_count[char] < target_count[char]:
                formed -= 1
            left += 1
        right += 1

    return "" if min_len == float('inf') else s[min_start:min_start + min_len]

# Fixed window: maximum of each window size k
def max_sliding_window(arr, k):
    if k > len(arr) or k == 0:
        return []
    from collections import deque
    result = []
    dq = deque()

    for i in range(len(arr)):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove smaller elements
        while dq and arr[dq[-1]] < arr[i]:
            dq.pop()
        dq.append(i)
        # Add result when window is full
        if i >= k - 1:
            result.append(arr[dq[0]])
    return result

# Test cases
print(max_sum_k([1, 2, 3, 4, 5], 3))  # 12
print(longest_substring_without_repeating("abcabcbb"))  # 3 ("abc")
print(min_window_substring("ADOBECODEBANC", "ABC"))  # "BANC"
print(max_sliding_window([1, 3, 1, 2, 0, 5], 3))  # [3, 3, 2, 5]

Common Pitfalls​

warning

Incorrect window boundary updates: Moving pointers in wrong order causes including/excluding wrong elements. Always remove from left, then add from right within iteration.

Not updating state correctly: Forgot to add/remove element contribution from running values. State must stay synchronized with window boundaries.

Off-by-one in valid condition: While loop condition determines when window is valid. < vs <= errors cause including extra or missing required elements.

Confusing right/left pointer significance: Right pointer moves forward through new elements, left moves forward to contract. Mixing them reverses logic.

Deque misuse in max window: Indices in deque must maintain decreasing order of values. Properly remove both front (outside window) and back (smaller values).

Self-Check​

  1. Why is sliding window O(n) despite appearing to have nested while loops? Trace through element addition/removal.
  2. Explain how to track "valid window" state in minimum window substring problem. What counts as valid?
  3. How does deque maintain maximum/minimum efficiently? Why can't you just store the value?

One Takeaway​

info

Sliding window transforms nested O(n²) approaches into linear O(n) solutions. The key is recognizing that each element is processed at most twice (added once by right pointer, removed once by left pointer). Mastering state management within windows and recognizing when to expand versus contract enables solving complex substring/subarray problems elegantly.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.