Introduction

The Sliding Window technique is an algorithmic paradigm for efficiently handling problems that involve contiguous subarrays or substrings. It involves maintaining a "window" (a subset of consecutive elements) and sliding it across the data structure (array or string) to avoid re-computation. This approach often reduces time complexity from O(n²) to O(n) by reusing results from the previous window.

In coding interviews, sliding window patterns arise in problems like finding subarrays with a given sum, maximum/minimum sum of a subarray of length k, or the longest substring meeting a condition (e.g., all unique characters). Keywords like “contiguous subarray,” “substring,” or constraints hinting at an O(n) solution often suggest this technique.

Fixed-Size Window Variants

In a fixed-size sliding window, we maintain a window of length k and slide it across the data one step at a time. The base template involves updating a window state (like a running sum) by adding the new element and removing the element that leaves the window.

1. Maximum Sum of Subarray of Size K LC 643

Template Adjustment: Maintain a running sum. When window reaches size k, update max sum, then subtract element leaving.

Problem: Maximum Average Subarray I (LeetCode 643). Find contiguous subarray of length k with max average (equiv. to max sum).

def findMaxAverage(nums, k):
    n = len(nums)
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum / k

2. Sliding Window Maximum LC 239

Template Adjustment: Use a deque to store indices of useful elements. Deque front is always index of current window's max. Pop from back if new element is larger; pop from front if index out of window.

Problem: Sliding Window Maximum (LeetCode 239). Return max value in each window of size k.

from collections import deque
def maxSlidingWindow(nums, k):
    dq = deque(); result = []
    for i, val in enumerate(nums):
        if dq and dq[0] == i - k: dq.popleft() # Remove out-of-window
        while dq and nums[dq[-1]] <= val: dq.pop() # Remove smaller from back
        dq.append(i)
        if i >= k - 1: result.append(nums[dq[0]])
    return result

3. Find All Anagrams in a String LC 438

Template Adjustment: Window slides over string s, size len(p). Maintain frequency counts of chars in window and compare to p's frequency.

Problem: Find All Anagrams in a String (LeetCode 438). Return start indices of s's substrings that are anagrams of p.

def findAnagrams(s, p):
    res = []
    if len(p) > len(s): return res
    target_counts = [0]*26
    window_counts = [0]*26
    for ch in p: target_counts[ord(ch) - ord('a')] += 1
    
    for i in range(len(p)):
        window_counts[ord(s[i]) - ord('a')] += 1
    if window_counts == target_counts: res.append(0)
        
    for end in range(len(p), len(s)):
        window_counts[ord(s[end]) - ord('a')] += 1
        window_counts[ord(s[end - len(p)]) - ord('a')] -= 1
        if window_counts == target_counts:
            res.append(end - len(p) + 1)
    return res

4. Permutation in String LC 567

Template Adjustment: Similar to anagrams, fixed window of size len(s1) over s2. Maintain char counts. Early exit if permutation found.

Problem: Permutation in String (LeetCode 567). Return true if any permutation of s1 is a substring of s2.

def checkInclusion(s1, s2):
    if len(s1) > len(s2): return False
    s1_counts = [0] * 26
    s2_window_counts = [0] * 26
    for ch in s1: s1_counts[ord(ch) - ord('a')] += 1

    left = 0
    for right in range(len(s2)):
        s2_window_counts[ord(s2[right]) - ord('a')] += 1
        if right - left + 1 > len(s1):
            s2_window_counts[ord(s2[left]) - ord('a')] -= 1
            left += 1
        if s1_counts == s2_window_counts: return True
    return False

5. Sliding Window Median LC 480

Template Adjustment: Use two heaps (max-heap for lower half, min-heap for upper half) to find median in O(log k). Add new element, rebalance heaps. Remove outgoing element (lazy deletion often used).

Problem: Sliding Window Median (LeetCode 480). Return array of medians for each window of size k.

import heapq
def medianSlidingWindow(nums, k):
    max_h, min_h = [], [] # max_h stores -num for lower half
    res = []
    invalid_counts = {} # For lazy deletion

    def add_num(num):
        if not max_h or num <= -max_h[0]: heapq.heappush(max_h, -num)
        else: heapq.heappush(min_h, num)
        balance_heaps()

    def remove_num(num):
        invalid_counts[num] = invalid_counts.get(num, 0) + 1
        balance_heaps() # Clean up invalid tops during balance

    def balance_heaps():
        # Clean invalid tops first
        while max_h and invalid_counts.get(-max_h[0], 0) > 0:
            val = -heapq.heappop(max_h)
            invalid_counts[val] -= 1
        while min_h and invalid_counts.get(min_h[0], 0) > 0:
            val = heapq.heappop(min_h)
            invalid_counts[val] -= 1
        
        # Actual balancing
        if len(max_h) > len(min_h) + 1: heapq.heappush(min_h, -heapq.heappop(max_h))
        elif len(min_h) > len(max_h): heapq.heappush(max_h, -heapq.heappop(min_h))
        # Ensure max_h has more or equal elements for odd k
        if len(min_h) > len(max_h): heapq.heappush(max_h, -heapq.heappop(min_h))


    def get_median():
        balance_heaps() # Ensure heaps are clean and balanced before getting median
        if k % 2 == 1: return float(-max_h[0])
        else: return (-max_h[0] + min_h[0]) / 2.0

    for i in range(k): add_num(nums[i])
    res.append(get_median())

    for i in range(k, len(nums)):
        remove_num(nums[i-k])
        add_num(nums[i])
        res.append(get_median())
    return res

Variable-Size Window Variants

The window size is not fixed. Expand window (move right pointer) to satisfy a condition, then shrink (move left pointer) to restore or optimize the condition.

1. Longest Substring Without Repeating Characters LC 3

Pattern: Expand window until duplicate char encountered. Shrink from left until window unique again. Use set/map for char tracking.

Problem: Longest Substring Without Repeating Characters (LeetCode 3).

def lengthOfLongestSubstring(s: str) -> int:
    seen_chars = set()
    max_len = 0
    left = 0
    for right in range(len(s)):
        while s[right] in seen_chars:
            seen_chars.remove(s[left])
            left += 1
        seen_chars.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

2. Fruit Into Baskets LC 904

Pattern: Longest subarray with ≤ 2 distinct values. Use map for fruit counts. Expand window; if > 2 distinct types, shrink from left.

Problem: Fruit Into Baskets (LeetCode 904). Max fruit from trees with at most 2 types.

def totalFruit(fruits: list[int]) -> int:
    counts = {}
    max_len = 0
    left = 0
    for right, fruit in enumerate(fruits):
        counts[fruit] = counts.get(fruit, 0) + 1
        while len(counts) > 2:
            counts[fruits[left]] -= 1
            if counts[fruits[left]] == 0:
                del counts[fruits[left]]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

3. Longest Repeating Character Replacement LC 424

Pattern: Longest substring where ≤ k chars can be replaced to make all same. Window valid if len - max_freq_char_count ≤ k. Expand window; if invalid, shrink from left.

Problem: Longest Repeating Character Replacement (LeetCode 424).

def characterReplacement(s: str, k: int) -> int:
    counts = {}
    max_freq = 0
    max_len = 0
    left = 0
    for right in range(len(s)):
        counts[s[right]] = counts.get(s[right], 0) + 1
        max_freq = max(max_freq, counts[s[right]])
        if (right - left + 1) - max_freq > k:
            counts[s[left]] -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

4. Minimum Window Substring LC 76

Pattern: Expand window until it covers all required chars from t. Then contract from left to find smallest valid window. Use frequency maps for t and current window.

Problem: Minimum Window Substring (LeetCode 76). Given s and t, find min window in s containing all chars of t.

def minWindow(s: str, t: str) -> str:
    if not t or not s or len(t) > len(s): return ""
    
    need_map = {}
    for char in t: need_map[char] = need_map.get(char, 0) + 1
    
    required_distinct_chars = len(need_map)
    formed_distinct_chars = 0
    
    window_counts = {}
    left, right = 0, 0
    min_len = float('inf')
    result_indices = (0, 0)

    while right < len(s):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        if char in need_map and window_counts[char] == need_map[char]:
            formed_distinct_chars += 1
            
        while left <= right and formed_distinct_chars == required_distinct_chars:
            current_len = right - left + 1
            if current_len < min_len:
                min_len = current_len
                result_indices = (left, right + 1)
            
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in need_map and window_counts[left_char] < need_map[left_char]:
                formed_distinct_chars -= 1
            left += 1
        right += 1
        
    return s[result_indices[0]:result_indices[1]] if min_len != float('inf') else ""

5. Minimum Size Subarray Sum LC 209

Pattern: Expand window until sum ≥ target. Then shrink from left to find smallest window still meeting sum ≥ target.

Problem: Minimum Size Subarray Sum (LeetCode 209). Given array of positive ints and target, find min length of contiguous subarray with sum ≥ target.

def minSubArrayLen(target: int, nums: list[int]) -> int:
    min_len = float('inf')
    current_sum = 0
    left = 0
    for right in range(len(nums)):
        current_sum += nums[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return 0 if min_len == float('inf') else min_len

Interactive Animation (Max Sum Subarray of Size K)

This animation demonstrates the fixed-size sliding window technique for finding the maximum sum of a subarray of a given size k.

General Time & Space Complexity (Sliding Window)

Time Complexity: Most sliding window algorithms achieve O(N) time complexity, where N is the size of the input array or string. This is because each element is typically processed by the left and right pointers at most once. Some variants, like Sliding Window Median using heaps, might be O(N log k) where k is the window size.

Space Complexity: Often O(k) or O(1).

• O(1) if only a few variables are needed to track window state (e.g., simple sum).
• O(k) if storing window elements (e.g., in a deque for Sliding Window Maximum) or using frequency maps/sets for k distinct elements. For character-based problems, this might be O(alphabet_size), which is constant.

General Common Pitfalls (Sliding Window)

• Off-by-One Errors: Incorrectly handling window boundaries (left, right) or calculating window length (right - left + 1).
• Forgetting to Update State: Not correctly adding the effect of the new element entering or removing the effect of the old element leaving the window.
• Inefficient Window Updates: Recalculating window aggregates from scratch (e.g., sum) instead of incremental updates. This negates the O(N) benefit.
• Misidentifying Window Type: Using a fixed-size approach for a variable-size problem or vice-versa.
• Stalled Window / Infinite Loops: In variable-size windows, ensure the left pointer always moves forward when shrinking conditions are met to guarantee termination.
• Edge Cases: Empty input, window size k larger than array, no valid window found, all elements identical, etc.
• Integer Overflow: For sum-based problems with large numbers, ensure the sum variable can handle large values.