🪟 Sliding Window Pattern

🪟 What Is the Sliding Window Pattern?

The Sliding Window pattern is a technique that processes a contiguous subarray or substring by maintaining a "window" that slides across the data structure. Instead of recomputing the result for each new window from scratch — which costs O(n·k) — you incrementally update by removing the element that left and adding the element that entered, achieving O(n) time complexity.

It is one of the most frequently tested patterns in FAANG interviews, appearing in problems related to subarrays, substrings, stream data, and optimization under constraints.

🎯 When to Use Sliding Window

Recognize these signals in a problem statement to reach for the sliding window technique:

• The problem involves a contiguous subarray or substring
• You need to find a maximum, minimum, longest, or shortest subarray/substring
• The problem mentions a fixed window size k or a constraint (at most k distinct, sum ≥ target)
• A brute-force solution is O(n²) and you need to optimize to O(n)
• The problem involves character frequencies or counts in a window

🔬 The 4 Sliding Window Sub-patterns

Pattern 1: Fixed-Size Window

The window size never changes. Initialize the window for the first k elements, then slide right by adding one element and removing one.

def fixed_window(arr, k):
    # Build the initial window
    window_sum = sum(arr[:k])
    result = window_sum

    for i in range(k, len(arr)):
        # Slide: add new right element, remove old left element
        window_sum += arr[i] - arr[i - k]
        result = max(result, window_sum)

    return result

Classic problems: 643. Maximum Average Subarray I, 346. Moving Average from Data Stream

Pattern 2: Variable-Size Window

Expand the right pointer unconditionally. When the constraint is violated, shrink from the left until the constraint is restored. The answer is tracked throughout.

def variable_window(s, k):
    from collections import defaultdict
    freq = defaultdict(int)
    left = 0
    result = 0

    for right in range(len(s)):
        freq[s[right]] += 1           # expand window

        while len(freq) > k:           # constraint violated
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1                   # shrink from left

        result = max(result, right - left + 1)

    return result

Classic problems: 3. Longest Substring Without Repeating Characters, 904. Fruit Into Baskets, 209. Minimum Size Subarray Sum

Pattern 3: Monotonic Deque (Max/Min in Window)

When you need the maximum or minimum of the current window in O(1), maintain a deque of indices whose values form a decreasing (for max) or increasing (for min) sequence. Remove elements outside the window and smaller/larger elements that are no longer useful.

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()        # stores indices, values are decreasing
    result = []

    for i, num in enumerate(nums):
        # Remove indices outside window
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements (they'll never be the max)
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])  # front is always the max

    return result

Pattern 4: Frequency Matching Window

Used when the window must contain all characters of a target string (possibly with extra characters). Track a "formed" count — how many characters in the window have met their required frequency. When formed equals the number of unique characters in target, you have a valid window.

from collections import Counter

def minWindow(s, t):
    need = Counter(t)
    have, total = 0, len(need)
    window = {}
    res, res_len = [-1, -1], float("inf")
    left = 0

    for right in range(len(s)):
        window[s[right]] = window.get(s[right], 0) + 1
        if s[right] in need and window[s[right]] == need[s[right]]:
            have += 1

        while have == total:
            if (right - left + 1) < res_len:
                res, res_len = [left, right], right - left + 1
            window[s[left]] -= 1
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1
            left += 1

    l, r = res
    return s[l:r+1] if res_len != float("inf") else ""

📋 All Sliding Window LeetCode Problems

22 curated problems across 3 sub-patterns. Start with Fixed Window, progress to Variable and Monotonic Deque.

💡 Interview Tips & Common Mistakes

❓ Sliding Window FAQ

🔗 Related Guides & Resources

• Two Pointers Pattern Guide – LeetCode Problems & Templates — master the foundational two-pointer technique
• Practice Sliding Window on the Tracker — track your progress across all 28 problems
• Full DSA Patterns Tracker — all 88 patterns in one place
• 8-Week Interview Study Plan — where sliding window fits