Sliding Window Pattern | Fixed & Variable Subarrays in O(n)
이 글의 핵심
Sliding window techniques scan contiguous segments in linear time: know when the window length is fixed vs driven by a sum or character constraint.
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)) # 2Fixed vs variable windows
| Fixed size | Variable size | |
|---|---|---|
| Length | Always k (or fixed rule) | Grows/shrinks with constraints |
| Typical loop | Advance right; when window length is k, update and shift left | Expand with right; while invalid, shrink from left |
| Examples | Max sum/average of length k, fixed-length anagram check | Minimum subarray sum, longest unique substring, minimum window substring |
| Relation to two pointers | Can express left = right - k + 1 | Same 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)) # 6Longest 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")) # 3Find 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
| Problem | Type | Idea |
|---|---|---|
| 3. Longest Substring Without Repeating Characters | Variable, no duplicates | Add right; while duplicate, shrink left |
| 76. Minimum Window Substring | Variable, need/cover | Expand until need met; shrink for minimality |
| 643. Maximum Average Subarray I | Fixed k | Slide: 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:
leftandrighteach move at most n steps → O(n) total. - Hash maps / counters: usually O(1) or O(σ) per step (alphabet size σ).
Expand / shrink patterns
- Expand (
right) — include the next element (fixed window: always step; variable: until a condition holds). - Shrink (
left) — fixed: keep length k; variable: while invalid or while you can improve minimality. - Invariant — write one sentence (“no duplicate chars”, “sum ≥ target”) to know when to run
while left ….
Pattern templates
# 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
- Sliding window: contiguous segments in O(n).
- Fixed: constant window length.
- Variable: expand/shrink by constraints.
- Goal: avoid O(n²) recomputation.
Practice links
Baekjoon: 2003, 21921
Programmers: Jewelry Shopping
LeetCode: 3, 438
Related posts
- Greedy algorithms
- Algorithm series index
- Arrays and lists
- Stacks and queues