Sliding Window - The Loop Killer

"Thấy O(N²)? Đừng chấp nhận. Tìm cách Slide." - HPN

Định nghĩa

Sliding Window là kỹ thuật dùng hai con trỏ để duyệt qua array/string một cách hiệu quả:

Duy trì một "cửa sổ" liên tục (contiguous subarray)
Mở rộng window bằng cách di chuyển right pointer
Thu hẹp window bằng cách di chuyển left pointer

📘 Core Insight

Thay vì tính lại từ đầu cho mỗi subarray → Reuse kết quả của window trước, chỉ cập nhật phần thay đổi.

Tại sao cần Sliding Window?

Bài toán: Maximum Sum Subarray of Size K

Tìm subarray kích thước K có tổng lớn nhất.

Approach	Time Complexity	1 triệu elements, K=1000
Brute-force	$O (N \times K)$	1 tỷ operations
Sliding Window	$O (N)$	1 triệu operations

🎯 THE WASTE

Brute-force: sum(arr[i:i+K]) tính lại toàn bộ K phần tử mỗi lần.

Sliding Window: Chỉ trừ 1, cộng 1 khi slide.

Window [1,2,3,4] sum = 10
Slide right: -1, +5 → Window [2,3,4,5] sum = 10 - 1 + 5 = 14

Mô hình hóa

Fixed Size Window

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K = 5

Step 1: [1, 3, 2, 6, -1] → sum = 11
         L           R

Step 2:    [3, 2, 6, -1, 4] → sum = 11 - 1 + 4 = 14
            L           R

Step 3:       [2, 6, -1, 4, 1] → sum = 14 - 3 + 1 = 12
               L           R

Variable Size Window

Problem: Smallest subarray with sum ≥ S

Array: [2, 1, 5, 2, 3, 2], S = 7

Window: [2, 1, 5] sum=8 ≥ 7 → Shrink!
        L     R
        
Window:    [1, 5] sum=6 < 7 → Expand!
            L  R

Window:    [1, 5, 2] sum=8 ≥ 7 → Shrink!
            L     R
            
Window:       [5, 2] sum=7 ≥ 7 → Answer: length 2!
               L  R

Hai Loại Sliding Window

1. Fixed-Size Window

Pattern:

Window size luôn = K
left và right di chuyển cùng tốc độ

2. Variable-Size Window

Pattern:

Expand right để tìm valid window
Shrink left để optimize (tìm min) hoặc invalidate

Production Implementation

python

# HPN Engineering Standard
# Implementation: Sliding Window Patterns

from typing import List, Optional, Tuple
from collections import defaultdict


# ============================================
# PATTERN 1: FIXED-SIZE WINDOW
# ============================================

def max_sum_subarray_k(arr: List[int], k: int) -> int:
    """
    Find maximum sum of any contiguous subarray of size k.
    
    Time: O(N)
    Space: O(1)
    
    Example:
        arr = [2, 1, 5, 1, 3, 2], k = 3
        → Maximum sum is 5 + 1 + 3 = 9
    """
    if len(arr) < k:
        return 0
    
    # Calculate sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(arr)):
        # Remove element leaving window, add element entering
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum


def find_averages_of_subarrays(arr: List[int], k: int) -> List[float]:
    """
    Find averages of all contiguous subarrays of size k.
    
    Time: O(N)
    Space: O(N-K+1) for result
    """
    if len(arr) < k:
        return []
    
    result = []
    window_sum = sum(arr[:k])
    result.append(window_sum / k)
    
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        result.append(window_sum / k)
    
    return result


# ============================================
# PATTERN 2: VARIABLE-SIZE WINDOW
# ============================================

def smallest_subarray_with_sum(arr: List[int], target_sum: int) -> int:
    """
    Find smallest contiguous subarray with sum ≥ target_sum.
    
    Time: O(N) - Each element visited at most twice
    Space: O(1)
    
    Example:
        arr = [2, 1, 5, 2, 3, 2], target = 7
        → Smallest subarray is [5, 2] with length 2
    
    Returns:
        Length of smallest subarray, or 0 if no such subarray exists
    """
    min_length = float('inf')
    window_sum = 0
    left = 0
    
    for right in range(len(arr)):
        # Expand window
        window_sum += arr[right]
        
        # Shrink window while sum is sufficient
        while window_sum >= target_sum:
            min_length = min(min_length, right - left + 1)
            window_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0


def longest_substring_k_distinct(s: str, k: int) -> str:
    """
    Find longest substring with at most K distinct characters.
    
    Time: O(N)
    Space: O(K) for character frequency map
    
    Example:
        s = "araaci", k = 2
        → Longest substring is "araa" (length 4)
    """
    if not s or k == 0:
        return ""
    
    char_freq = defaultdict(int)
    max_length = 0
    max_start = 0
    left = 0
    
    for right in range(len(s)):
        # Expand window
        char_freq[s[right]] += 1
        
        # Shrink window if too many distinct chars
        while len(char_freq) > k:
            char_freq[s[left]] -= 1
            if char_freq[s[left]] == 0:
                del char_freq[s[left]]
            left += 1
        
        # Update max
        if right - left + 1 > max_length:
            max_length = right - left + 1
            max_start = left
    
    return s[max_start:max_start + max_length]


# ============================================
# PATTERN 3: TWO-POINTER VARIANT
# ============================================

def max_fruits_in_baskets(fruits: List[int], num_baskets: int) -> int:
    """
    Maximum number of fruits you can pick with K baskets.
    Each basket can only hold one type of fruit.
    
    This is equivalent to: longest subarray with at most K distinct elements.
    
    Time: O(N)
    Space: O(K)
    """
    basket_counts = defaultdict(int)
    max_fruits = 0
    left = 0
    
    for right in range(len(fruits)):
        # Pick fruit
        basket_counts[fruits[right]] += 1
        
        # Too many fruit types → shrink
        while len(basket_counts) > num_baskets:
            basket_counts[fruits[left]] -= 1
            if basket_counts[fruits[left]] == 0:
                del basket_counts[fruits[left]]
            left += 1
        
        max_fruits = max(max_fruits, right - left + 1)
    
    return max_fruits


# ============================================
# PATTERN 4: SLIDING WINDOW WITH HASHMAP
# ============================================

def find_anagrams(text: str, pattern: str) -> List[int]:
    """
    Find all starting indices of pattern's anagrams in text.
    
    Time: O(N)
    Space: O(K) where K = number of unique chars in pattern
    
    Example:
        text = "cbaebabacd", pattern = "abc"
        → Anagrams start at indices [0, 6]
    """
    if len(pattern) > len(text):
        return []
    
    pattern_count = defaultdict(int)
    window_count = defaultdict(int)
    
    for c in pattern:
        pattern_count[c] += 1
    
    result = []
    k = len(pattern)
    
    for i in range(len(text)):
        # Add to window
        window_count[text[i]] += 1
        
        # Remove from window if size exceeded
        if i >= k:
            left_char = text[i - k]
            window_count[left_char] -= 1
            if window_count[left_char] == 0:
                del window_count[left_char]
        
        # Check if anagram
        if window_count == pattern_count:
            result.append(i - k + 1)
    
    return result


# ============================================
# USAGE EXAMPLE
# ============================================
if __name__ == "__main__":
    # Fixed-size window
    arr = [2, 1, 5, 1, 3, 2]
    print(f"Max sum of subarray (k=3): {max_sum_subarray_k(arr, 3)}")
    # Output: 9 (subarray [5, 1, 3])
    
    # Variable-size window
    arr = [2, 1, 5, 2, 3, 2]
    print(f"Smallest subarray with sum ≥ 7: {smallest_subarray_with_sum(arr, 7)}")
    # Output: 2 (subarray [5, 2])
    
    # Longest substring
    s = "araaci"
    print(f"Longest substring with 2 distinct: '{longest_substring_k_distinct(s, 2)}'")
    # Output: "araa"
    
    # Find anagrams
    text = "cbaebabacd"
    pattern = "abc"
    print(f"Anagram positions: {find_anagrams(text, pattern)}")
    # Output: [0, 6]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

Interview Signal Words

Khi nào dùng Sliding Window:

Signal	Example Problem
"Contiguous subarray"	Max sum subarray of size K
"Substring"	Longest substring without repeating
"At most K"	Subarray with at most K distinct
"Minimum length"	Smallest subarray with sum ≥ S
"Maximum length"	Longest substring with K replacements

Anti-patterns

❌ TRÁNH

1. Không nhận ra Sliding Window applicable

python

# ❌ WRONG: O(N²) brute force
def max_sum_k(arr, k):
    max_sum = 0
    for i in range(len(arr) - k + 1):
        max_sum = max(max_sum, sum(arr[i:i+k]))  # O(N*K)!
    return max_sum

# ✅ RIGHT: O(N) sliding window (xem implementation ở trên)

2. Nhầm fixed-size với variable-size

python

# ❌ WRONG: Dùng fixed window cho variable problem
def smallest_subarray(arr, target):
    for k in range(1, len(arr)):  # Try all sizes ← O(N²)!
        for i in range(len(arr) - k + 1):
            if sum(arr[i:i+k]) >= target:
                return k

# ✅ RIGHT: Variable window, shrink when valid

3. Quên xử lý edge case

python

# ❌ WRONG: len(arr) < k gây index error
window_sum = sum(arr[:k])  # Crash if k > len(arr)

# ✅ RIGHT: Handle edge case
if len(arr) < k:
    return 0  # or raise ValueError

💡 HPN's Rule

"Thấy 'contiguous' + 'subarray/substring' → Slide. Không cần nghĩ."

Sliding Window - The Loop Killer ​

Định nghĩa ​

Tại sao cần Sliding Window? ​

Bài toán: Maximum Sum Subarray of Size K ​

Mô hình hóa ​

Fixed Size Window ​

Variable Size Window ​

Hai Loại Sliding Window ​

1. Fixed-Size Window ​

2. Variable-Size Window ​

Production Implementation ​

Interview Signal Words ​

Anti-patterns ​

Sliding Window - The Loop Killer

Định nghĩa

Tại sao cần Sliding Window?

Bài toán: Maximum Sum Subarray of Size K

Mô hình hóa

Fixed Size Window

Variable Size Window

Hai Loại Sliding Window

1. Fixed-Size Window

2. Variable-Size Window

Production Implementation

Interview Signal Words

Anti-patterns