Sliding Window Pattern | Fixed & Variable Subarrays in O(n)

Sliding Window Pattern | Fixed & Variable Subarrays in O(n)

· 22분 읽기 · 수정 Intermediate Tutorial
Sliding Window Pattern | Fixed & Variable Subarrays in O(n)

이 글의 핵심

Sliding window algorithm: fixed and variable windows on arrays and strings—max sum, minimum size subarray, longest unique substring, anagrams—with Python and complexity notes.

Introduction

Recomputing every contiguous segment from scratch is often too slow. Sliding window updates the current segment in O(1) amortized work as you move one step at a time, yielding O(n) overall.

Sliding the window for optimization

A sliding window is a contiguous subarray or substring maintained while scanning the input.

1. Fixed-size window

Basic pattern

def max_sum_subarray(arr, k):
    """
    Maximum sum of a subarray of length k.
    [1, 4, 2, 10, 23, 3, 1, 0, 20], k=4 -> 39
    """
    if len(arr) < k:
        return None
    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
# Test
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
print(max_sum_subarray(arr, 4))  # 39 (10+23+3+1)

2. Variable-size window

Minimum length subarray with sum ≥ target

def min_subarray_len(arr, target):
    """
    Smallest length of a subarray with sum >= target.
    [2,3,1,2,4,3], target=7 -> 2 ([4,3])
    """
    left = 0
    current_sum = 0
    min_len = float('inf')
    for right in range(len(arr)):
        current_sum += arr[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
    return min_len if min_len != float('inf') else 0
# Test
arr = [2, 3, 1, 2, 4, 3]
print(min_subarray_len(arr, 7))  # 2

Fixed vs variable windows

Fixed sizeVariable size
LengthAlways k (or fixed rule)Grows/shrinks with constraints
Typical loopAdvance right; when window length is k, update and shift leftExpand with right; while invalid, shrink from left
ExamplesMax sum/average of length k, fixed-length anagram checkMinimum subarray sum, longest unique substring, minimum window substring
Relation to two pointersCan express left = right - k + 1Same forward-only two-pointer idea with a length rule
Both use left and right only moving forward; the difference is whether length is fixed or data-dependent.

3. More examples

Longest subarray with at most k zeros (flip bits)

def longest_ones(arr, k):
    """
    Max consecutive 1s if you may flip at most k zeros.
    [1,1,1,0,0,0,1,1,1,1,0], k=2 -> 6
    """
    left = 0
    zero_count = 0
    max_len = 0
    for right in range(len(arr)):
        if arr[right] == 0:
            zero_count += 1
        while zero_count > k:
            if arr[left] == 0:
                zero_count -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len
# Test
arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
print(longest_ones(arr, 2))  # 6

Longest substring without repeating characters

def length_of_longest_substring(s):
    """
    Length of longest substring with no duplicate characters.
    "abcabcbb" -> 3 ("abc")
    """
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len
# Tests
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))     # 1
print(length_of_longest_substring("pwwkew"))    # 3

Find all anagrams

from collections import Counter
def find_anagrams(s, p):
    """
    Starting indices in s where the substring is an anagram of p.
    s="cbaebabacd", p="abc" -> [0, 6]
    """
    result = []
    p_count = Counter(p)
    window_count = Counter()
    left = 0
    for right in range(len(s)):
        window_count[s[right]] += 1
        if right - left + 1 > len(p):
            window_count[s[left]] -= 1
            if window_count[s[left]] == 0:
                del window_count[s[left]]
            left += 1
        if window_count == p_count:
            result.append(left)
    return result
# Test
print(find_anagrams("cbaebabacd", "abc"))

Classic LeetCode trio

ProblemTypeIdea
3. Longest Substring Without Repeating CharactersVariable, no duplicatesAdd right; while duplicate, shrink left
76. Minimum Window SubstringVariable, need/coverExpand until need met; shrink for minimality
643. Maximum Average Subarray IFixed kSlide: subtract outgoing, add incoming

Minimum window sketch

from collections import Counter
def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = 0
    best = (float("inf"), None, None)
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best[1] is None else s[best[1] : best[2] + 1]

Complexity

  • Brute force: enumerate all [left, right] pairs → O(n²)–O(n³).
  • Sliding window: left and right each move at most n steps → O(n) total.
  • Hash maps / counters: usually O(1) or O(σ) per step (alphabet size σ).

Expand / shrink patterns

  1. Expand (right) — include the next element (fixed window: always step; variable: until a condition holds).
  2. Shrink (left) — fixed: keep length k; variable: while invalid or while you can improve minimality.
  3. Invariant — write one sentence (“no duplicate chars”, “sum ≥ target”) to know when to run while left ….

Pattern templates

The following example demonstrates the concept in python:

# Fixed size
left = 0
for right in range(len(arr)):
    add(arr[right])
    if right - left + 1 == k:
        process_window()
        remove(arr[left])
        left += 1
# Variable size
left = 0
for right in range(len(arr)):
    add(arr[right])
    while not is_valid():
        remove(arr[left])
        left += 1
    update_result()

Summary

  1. Sliding window: contiguous segments in O(n).
  2. Fixed: constant window length.
  3. Variable: expand/shrink by constraints.
  4. Goal: avoid O(n²) recomputation.

Baekjoon: 2003, 21921
Programmers: Jewelry Shopping
LeetCode: 3, 438

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Sliding window algorithm: fixed and variable windows on arrays and strings—max sum, minimum size subarray, longest.

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

Other articles related to this topic.

Keywords Covered in This Article (Related Search Terms)

This article covers Algorithm, Sliding Window, Arrays, Strings, Coding Interview.