When to use sliding window?

Use for subarray/substring problems to optimize O(n²) → O(n).

Difference from two pointers?

Sliding window handles contiguous ranges, two pointers move freely based on conditions.

Difference between fixed and variable size?

Fixed keeps window size constant, variable changes size based on conditions.

Sliding Window | Subarray Optimization Technique Complete Guide

2026년 3월 28일 · 22분 읽기 · 수정 2026년 3월 30일 Intermediate Tutorial

이 글의 핵심

Sliding window algorithm optimizes contiguous ranges by sliding one position at a time in O(n). Master fixed and variable window patterns with detailed examples.

Introduction

Recalculating sum or conditions of contiguous subarrays or substrings from scratch each time easily causes timeout. This guide teaches how to reduce complexity by sliding the window one position at a time and updating incrementally.

”Optimize by Sliding the Window”

Sliding window is a technique for efficiently processing contiguous subarrays.

1. Fixed-Size Window

Basic Pattern

def max_sum_subarray(arr, k):
    """
    Maximum sum of subarray of size k
    [1, 4, 2, 10, 23, 3, 1, 0, 20], k=4 → 39
    """
    if len(arr) < k:
        return None
    
    # First window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window
    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)

Step-by-Step Trace:

arr = [1, 4, 2, 10, 23, 3, 1, 0, 20], k=4

Initial window [0:4]: 1+4+2+10 = 17

Slide 1: Remove arr[0]=1, Add arr[4]=23
  [1:5]: 4+2+10+23 = 39 ✅ max

Slide 2: Remove arr[1]=4, Add arr[5]=3
  [2:6]: 2+10+23+3 = 38

Slide 3: Remove arr[2]=2, Add arr[6]=1
  [3:7]: 10+23+3+1 = 37

...

Result: 39

2. Variable-Size Window

Minimum Length Subarray

def min_subarray_len(arr, target):
    """
    Minimum length 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]
        
        # Shrink window when condition met
        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

How It Works:

arr = [2, 3, 1, 2, 4, 3], target=7

right=0: [2], sum=2 (< 7)
right=1: [2,3], sum=5 (< 7)
right=2: [2,3,1], sum=6 (< 7)
right=3: [2,3,1,2], sum=8 (>= 7) ✅
  Shrink: [3,1,2], sum=6 (< 7)
right=4: [3,1,2,4], sum=10 (>= 7) ✅
  Shrink: [1,2,4], sum=7 (>= 7) ✅
  Shrink: [2,4], sum=6 (< 7)
right=5: [2,4,3], sum=9 (>= 7) ✅
  Shrink: [4,3], sum=7 (>= 7) ✅ min_len=2
  Shrink: [3], sum=3 (< 7)

Result: 2

Fixed vs Variable Window

Feature	Fixed Size	Variable Size
Window Length	Always same (e.g., `k`)	Expands/shrinks based on conditions
Typical Loop	`right` advances, `left` advances when `right - left + 1 == k`	Expand with `right`, shrink with `left` until condition breaks
Representative Problems	Size k subarray sum/max, fixed-length anagram	Minimum length subarray sum, longest substring without repeating, minimum window substring
vs Two Pointers	Can express as `left = right - k + 1`	Same “expand/shrink pattern” two-pointer thinking

Both are same-direction two pointers where left and right only move forward. The difference is whether length is fixed.

3. Practical Problems

Problem 1: Max Consecutive Ones

def longest_ones(arr, k):
    """
    Maximum consecutive 1s when flipping 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
        
        # Shrink window if zeros exceed k
        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

Trace:

arr = [1,1,1,0,0,0,1,1,1,1,0], k=2

right=0-2: [1,1,1], zeros=0, len=3
right=3: [1,1,1,0], zeros=1, len=4
right=4: [1,1,1,0,0], zeros=2, len=5
right=5: [1,1,1,0,0,0], zeros=3 (> k)
  Shrink: [1,1,0,0,0], zeros=3
  Shrink: [1,0,0,0], zeros=3
  Shrink: [0,0,0], zeros=3
  Shrink: [0,0], zeros=2
right=6: [0,0,1], zeros=2, len=3
right=7: [0,0,1,1], zeros=2, len=4
right=8: [0,0,1,1,1], zeros=2, len=5
right=9: [0,0,1,1,1,1], zeros=2, len=6 ✅
right=10: [0,0,1,1,1,1,0], zeros=3 (> k)
  Shrink: [0,1,1,1,1,0], zeros=2, len=6

Result: 6

Problem 2: Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    """
    Longest substring without repeating characters
    "abcabcbb" → 3 ("abc")
    """
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        # Remove duplicates
        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

# Test
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))     # 1
print(length_of_longest_substring("pwwkew"))    # 3

Trace:

s = "abcabcbb"

right=0: 'a', set={'a'}, len=1
right=1: 'b', set={'a','b'}, len=2
right=2: 'c', set={'a','b','c'}, len=3 ✅
right=3: 'a' (duplicate!)
  Remove 'a', left=1, set={'b','c'}
  Add 'a', set={'b','c','a'}, len=3
right=4: 'b' (duplicate!)
  Remove 'b', left=2, set={'c','a'}
  Add 'b', set={'c','a','b'}, len=3
...

Result: 3

Problem 3: Find All Anagrams

from collections import Counter

def find_anagrams(s, p):
    """
    Find starting indices of p's anagrams in s
    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
        
        # Maintain window size
        if right - left + 1 > len(p):
            window_count[s[left]] -= 1
            if window_count[s[left]] == 0:
                del window_count[s[left]]
            left += 1
        
        # Check anagram
        if window_count == p_count:
            result.append(left)
    
    return result

# Test
print(find_anagrams("cbaebabacd", "abc"))
# [0, 6]

Representative Problems (LeetCode)

These three are almost essential when studying sliding window. (Good to read in connection with examples above.)

Problem	Type	Key
3. Longest Substring Without Repeating Characters	Variable, condition: no duplicates	Add with `right` → remove duplicates by pulling `left`
76. Minimum Window Substring	Variable, need/cover	Expand with `right` until need met → shrink with `left` for minimum
643. Maximum Average Subarray I	Fixed length k	Slide one position: `sum -= out, sum += in`, O(n)

Minimum Window Substring Sketch (Python)

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)  # length, start, end

    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]

(In actual submissions, separating need/window is common. Above is a minimal example emphasizing “condition met with missing count”.)

Time Complexity Analysis

Brute Force
Checking all contiguous ranges [left, right] with nested loops is O(n²)~O(n³).
Sliding Window
left and right each move forward at most n times, total O(n). (Even if left moves multiple times per right advance, since left never goes backward, combined is linear.)
Map/Counter
Maintaining character/frequency is O(1)~O(σ) per operation (alphabet size σ), usually expressed as O(n) or O(n·σ).
Fixed Size k
Initial sum O(k) + slide O(n−k) → O(n).

Window Expand/Shrink Condition Patterns

Expand (right++)
Always widen one position to include element in current range. Fixed window advances right sequentially, variable expands “to satisfy condition”.
Shrink (left++)
- Fixed size: If right - left + 1 > k, pull left one position to maintain length k.
- Variable — when invalid: e.g., duplicate characters, too many zeros, before finding “minimum length” after need met.
- Variable — when valid but can shrink more: In Minimum Window, after need met, pull left to update minimum length.
Invariant
Writing “condition window must satisfy” in one sentence clarifies when to pull left with while. (e.g., “move left until no duplicate characters”.)

Practical Tips

Sliding Window Patterns

# Pattern 1: 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

# Pattern 2: Variable size
left = 0
for right in range(len(arr)):
    add(arr[right])
    
    while not is_valid():
        remove(arr[left])
        left += 1
    
    update_result()

Common Patterns

# 1. Maximum/Minimum length
max_len = 0
for right in range(len(arr)):
    # Expand
    while not is_valid():
        # Shrink
        left += 1
    max_len = max(max_len, right - left + 1)

# 2. Count valid subarrays
count = 0
for right in range(len(arr)):
    while not is_valid():
        left += 1
    count += right - left + 1  # All subarrays ending at right

# 3. Fixed size k
for right in range(len(arr)):
    if right >= k:
        remove(arr[right - k])
    add(arr[right])
    if right >= k - 1:
        process_window()

4. Advanced Problems

Problem: Minimum Window Substring (LeetCode 76)

from collections import Counter

def min_window(s, t):
    """
    Minimum window substring containing all characters of t
    s="ADOBECODEBANC", t="ABC" → "BANC"
    """
    if not t or not s:
        return ""
    
    need = Counter(t)
    missing = len(t)
    left = 0
    min_len = float('inf')
    min_start = 0
    
    for right in range(len(s)):
        # Expand
        if need[s[right]] > 0:
            missing -= 1
        need[s[right]] -= 1
        
        # Shrink when valid
        while missing == 0:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left
            
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    
    return "" if min_len == float('inf') else s[min_start:min_start + min_len]

# Test
print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

Problem: Longest Repeating Character Replacement

def character_replacement(s, k):
    """
    Longest substring with same character after replacing k characters
    s="AABABBA", k=1 → 4 ("AABA" or "ABBB")
    """
    char_count = {}
    left = 0
    max_len = 0
    max_count = 0
    
    for right in range(len(s)):
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        max_count = max(max_count, char_count[s[right]])
        
        # If replacements needed > k, shrink
        while right - left + 1 - max_count > k:
            char_count[s[left]] -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len

# Test
print(character_replacement("AABABBA", 1))  # 4

Practical Tips

Coding Interview Tips

# ✅ Initialize properly
left = 0
window_state = {}  # or set(), Counter(), etc.

# ✅ Update window state
# Add when expanding (right)
# Remove when shrinking (left)

# ✅ Check boundary conditions
# - Empty array/string
# - k > len(arr)
# - All same elements

# ✅ Understand expand/shrink conditions
# Fixed: Expand until size k, then slide
# Variable: Expand always, shrink when invalid

Common Mistakes

# ❌ Wrong: Forgot to remove when shrinking
for right in range(len(arr)):
    add(arr[right])
    while not is_valid():
        left += 1  # Forgot to remove arr[left]!

# ✅ Correct: Remove before moving left
for right in range(len(arr)):
    add(arr[right])
    while not is_valid():
        remove(arr[left])
        left += 1

# ❌ Wrong: Incorrect window size check
if right - left == k:  # Should be right - left + 1

# ✅ Correct: Window size is right - left + 1
if right - left + 1 == k:

Summary

Key Points

Sliding Window: Process contiguous subarray in O(n)
Fixed Size: Window size constant
Variable Size: Expand/shrink based on conditions
Optimization: O(n²) → O(n)

Pattern Checklist

Pattern	Window Size	Movement	Example
Fixed	Constant k	Slide one position	Max sum size k
Variable (max)	Expand until invalid	Expand always, shrink when invalid	Longest substring
Variable (min)	Shrink until invalid	Expand until valid, shrink while valid	Minimum window

Keywords

Sliding Window, Algorithm, Optimization, Subarray, Substring, Fixed Window, Variable Window, Coding Interview, O(n), Two Pointers

Sliding Window | Subarray Optimization Technique Complete Guide

이 글의 핵심

Introduction

”Optimize by Sliding the Window”

1. Fixed-Size Window

Basic Pattern

2. Variable-Size Window

Minimum Length Subarray

Fixed vs Variable Window

3. Practical Problems

Problem 1: Max Consecutive Ones

Problem 2: Longest Substring Without Repeating Characters

Problem 3: Find All Anagrams

Representative Problems (LeetCode)

Minimum Window Substring Sketch (Python)

Time Complexity Analysis

Window Expand/Shrink Condition Patterns

Practical Tips

Sliding Window Patterns

Common Patterns

4. Advanced Problems

Problem: Minimum Window Substring (LeetCode 76)

Problem: Longest Repeating Character Replacement

Practical Tips

Coding Interview Tips

Common Mistakes

Summary

Key Points

Pattern Checklist

Recommended Problems

Baekjoon

LeetCode

Programmers

Keywords

이 글의 핵심

Introduction

”Optimize by Sliding the Window”

1. Fixed-Size Window

Basic Pattern

2. Variable-Size Window

Minimum Length Subarray

Fixed vs Variable Window

3. Practical Problems

Problem 1: Max Consecutive Ones

Problem 2: Longest Substring Without Repeating Characters

Problem 3: Find All Anagrams

Representative Problems (LeetCode)

Minimum Window Substring Sketch (Python)

Time Complexity Analysis

Window Expand/Shrink Condition Patterns

Practical Tips

Sliding Window Patterns

Common Patterns

4. Advanced Problems

Problem: Minimum Window Substring (LeetCode 76)

Problem: Longest Repeating Character Replacement

Practical Tips

Coding Interview Tips

Common Mistakes

Summary

Key Points

Pattern Checklist

Recommended Problems

Baekjoon

LeetCode

Programmers

Related Posts

Keywords