Previous
Next
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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Sliding window algorithm: fixed and variable windows on arrays and strings—max sum, minimum size subarray, longest uniqu… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Sliding Window, Arrays, Strings, Coding Interview 등으로 검색하시면 이 글이 도움이 됩니다.