[2026] Sliding Window | Subarray Optimization Technique Complete Guide

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

1. Expand (right++)
   Always widen one position to include element in current range. Fixed window advances right sequentially, variable expands “to satisfy condition”.
2. 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.
3. 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

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 비동기 처리를 통해 효율적으로 작업을 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ 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

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 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

1. Sliding Window: Process contiguous subarray in O(n)
2. Fixed Size: Window size constant
3. Variable Size: Expand/shrink based on conditions
4. 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

---

Recommended Problems

Baekjoon

• 2003: Sum of Numbers 2
• 21921: Blog

LeetCode

• LeetCode 3: Longest Substring Without Repeating Characters
• LeetCode 76: Minimum Window Substring
• LeetCode 438: Find All Anagrams in a String
• LeetCode 567: Permutation in String
• LeetCode 643: Maximum Average Subarray I
• LeetCode 1004: Max Consecutive Ones III

Programmers

• Jewelry Shopping

---

Related Posts

• Two Pointers | O(n²) → O(n) Optimization Technique Complete Guide
• Greedy Algorithm | “Best Choice Every Step” Complete Guide
• Algorithm Series Full Index
• Arrays and Lists

---

Keywords

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