When to Use Sliding Window?

Core Idea: Maintain a window (subarray/substring) and expand/shrink it based on conditions. Avoids recomputing from scratch (O(n²) → O(n)).

Pattern Recognition:

Window Types:

Variable Size: Expand right, shrink left when constraint violated. Track max/min length.

Fixed Size: Slide window of size k, add new element, remove old element.

Template:

i := 0 // left pointer for j := 0; j < n; j++: // right pointer // expand: add nums[j] to window for window_invalid: // shrink: remove nums[i] from window i++ // update result

Best Time to Buy/Sell Stock

O(n) Time / O(1) Space

Goal: Find max profit from buying low and selling high (buy before sell).

Technique: Track Minimum

Why Sliding Window? For each sell day, we need the minimum buy price before it. Instead of scanning left each time (O(n²)), track running minimum as we go. Window is implicitly [minBuy...currentDay].

Key Insight: At each position, we have two choices: (1) sell at current price (profit = price - minBuy), or (2) update minBuy if current is lower. No need to track window explicitly.

buy := prices[0] maxProfit := 0 for _, sell := range prices[1:]: maxProfit = max(maxProfit, sell - buy) if sell < buy: buy = sell // found better buy point

Simplest Pattern:

Track single state (minimum/maximum) as window expands.

Longest Substring Without Repeating Chars

O(n) Time / O(min(n,m)) Space

Goal: Find length of longest substring with all unique characters.

Technique: Variable Window + Set

Why Sliding Window? Brute force checks all substrings O(n²). With sliding window: expand right adding chars, shrink left when duplicate found. Each char processed at most twice (add once, remove once) = O(n).

Key Insight: Use set to track chars in current window. When new char already exists, shrink from left until it's removed. Window always contains unique chars.

inSubstr := map[rune]bool{} i := 0 res := 0 for j, char := range s: for i < j && inSubstr[char]: delete(inSubstr, rune(s[i])) i++ inSubstr[char] = true res = max(res, j - i + 1)

Trap:

Shrink loop must delete chars until duplicate removed, not just once.

Longest Repeating Char Replacement

O(n) Time / O(1) Space

Goal: With at most k replacements, find longest substring of same character.

Technique: Variable Window + Frequency

Why Sliding Window? Window is valid if: (window_length - max_freq) ≤ k. The chars NOT matching the most frequent char are what we'd replace. Expand right, shrink left when replacements exceed k.

Key Insight: Track frequency of each char in window. Chars to replace = windowLen - maxFreq. If this exceeds k, shrink window. maxFreq can be stale (not decremented) because we only care about finding longer valid windows.

count := [26]int{} maxFreq := 0 i := 0 res := 0 for j := 0; j < len(s); j++: count[s[j]-'A']++ maxFreq = max(maxFreq, count[s[j]-'A']) for (j - i + 1) - maxFreq > k: count[s[i]-'A']-- i++ res = max(res, j - i + 1)

Key Formula:

replacements_needed = window_length - max_frequency

Permutation in String

O(n) Time / O(1) Space

Goal: Check if s2 contains any permutation of s1 as substring.

Technique: Fixed Window + Frequency Match

Why Sliding Window? Permutation = same character counts in different order. Use fixed window of size len(s1). Slide through s2, comparing frequency arrays. If they match, permutation found.

Key Insight: Window size is fixed (len(s1)). Maintain frequency count of current window. Slide by adding new char, removing old char. Compare arrays in O(26) = O(1).

var count1, count2 [26]int // Initialize first window for i := 0; i < len(s1); i++: count1[s1[i]-'a']++ count2[s2[i]-'a']++ if count1 == count2: return true // Slide the window for i := len(s1); i < len(s2); i++: count2[s2[i]-'a']++ // add right count2[s2[i-len(s1)]-'a']-- // remove left if count1 == count2: return true

Fixed Window:

Size never changes. Only slide, don't expand/shrink.

Minimum Window Substring

O(n) Time / O(m) Space

Goal: Find shortest substring of s containing all chars of t.

Technique: Variable Window + Count Match

Why Sliding Window? Expand right until window contains all chars of t. Then shrink left to find minimum. Track "letters complete" to know when all t chars are satisfied.

Key Insight: Track two things: (1) frequency of each t char needed, (2) how many distinct chars have reached required count. When lettersComplete == len(tCount), window is valid. Shrink to find minimum.

tCount := map[rune]int{} // required counts for _, c := range t: tCount[c]++ lettersComplete := 0 currCount := map[rune]int{} i := 0 for j := 0; j < len(s); j++: // Expand: add s[j] if tFreq, ok := tCount[s[j]]; ok: currCount[s[j]]++ if currCount[s[j]] == tFreq: lettersComplete++ // Shrink while valid for lettersComplete == len(tCount): update result if smaller // remove s[i] if tFreq, ok := tCount[s[i]]; ok: currCount[s[i]]-- if currCount[s[i]] < tFreq: lettersComplete-- i++

Two Counts:

Track both required frequency and "satisfied" count.

Sliding Window Maximum

O(n) Time / O(k) Space

Goal: Return max element in each window of size k.

Technique: Fixed Window + Monotonic Deque

Why Deque? Naive approach: for each window, find max = O(nk). Deque maintains indices in decreasing order of values. Front is always the max. When new element comes, remove all smaller from back (they can never be max).

Key Insight: Deque stores potential maximums. When sliding: (1) remove front if out of window, (2) remove all back elements smaller than new (they're useless), (3) add new to back. Front is current max.

deque := []int{} // stores indices i, j := 0, 0 for j < len(nums): // Remove smaller elements from back for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[j]: deque = deque[:len(deque)-1] deque = append(deque, j) // Remove front if out of window if i > deque[0]: deque = deque[1:] // Record max when window is full if j + 1 >= k: output = append(output, nums[deque[0]]) i++ j++

Store Indices:

Store indices in deque, not values, to check window bounds.

Sliding Window Patterns Summary

1. Variable Window (Expand/Shrink):

Use When: Find longest/shortest subarray satisfying condition.

Examples: Longest Substring Without Repeating, Minimum Window Substring.

Template: Expand j, shrink i when invalid, track result at each step.

2. Fixed Window (Slide):

Use When: Window size is given (size k), or determined by input (permutation).

Examples: Permutation in String, Sliding Window Maximum.

Template: Initialize window, then slide: add right, remove left.

3. Track State (Min/Max/Frequency):

Use When: Need running min/max or character frequencies.

Examples: Best Time Buy/Sell (min), Char Replacement (maxFreq).

Key: Update state incrementally, don't recompute from scratch.

4. Monotonic Deque:

Use When: Need min/max in sliding window efficiently.

Examples: Sliding Window Maximum.

Key: Maintain decreasing (for max) or increasing (for min) order.

Common Thread:

All avoid O(n²) by maintaining window state incrementally. Expand/shrink or slide the window, updating state in O(1) per step.