Sliding Window

1. 1.Maximum Average Subarray I
   Fixed K sumeasy
2. 2.Maximum Sum Subarray of Size K
   Fixed window slideeasy
3. 3.Minimum Size Subarray Sum
   Shrink left when validmedium
4. 4.Longest Substring Without Repeating Characters
   Set/Map + shrink leftmedium
5. 5.Longest Repeating Character Replacement
   Freq map + maxFreqmedium
6. 6.Permutation in String
   Fixed K freq matchmedium
7. 7.Find All Anagrams in a String
   Fixed K freq mapmedium
8. 8.Minimum Window Substring
   Freq map + required matchhard
9. 9.Max Consecutive Ones III
   At most K zerosmedium
10. 10.Fruit Into Baskets
    At most 2 distinct elementsmedium
11. 11.Subarray Product Less Than K
    Product windowmedium
12. 12.Grumpy Bookstore Owner
    Fixed window boostmedium
13. 13.Maximum Points You Can Obtain from Cards
    Total sum - fixed windowmedium
14. 14.Sliding Window Maximum
    Monotonic Dequehard

1. 15.Contains Duplicate II
   Window size K seteasy
2. 16.Number of Sub-arrays of Size K and Average ≥ Threshold
   Fixed K sum checkmedium
3. 17.Minimum Recolors to Get K Consecutive Black Blocks
   Fixed K min whiteeasy
4. 18.Longest Subarray of 1's After Deleting One Element
   At most 1 zeromedium
5. 19.Frequency of the Most Frequent Element
   Sort + window costmedium
6. 20.Binary Subarrays With Sum
   AtMost(K) - AtMost(K-1)medium
7. 21.Count Number of Nice Subarrays
   AtMost(K) odd numbersmedium
8. 22.Minimum Operations to Reduce X to Zero
   Max window sum = Total - Xmedium

How to Think

1. Continuous part of array/string?Sliding Window
2. Fixed size K?Add new item, Remove old item
3. Longest / shortest valid substring?Expand right, Shrink left
4. Need no duplicates?Sliding Window + Hash Set / Hash Map
5. Need character frequency?Window + Frequency Map
6. Need max/min for every window?Sliding Window + Monotonic Deque

func maxSumFixed(nums []int, k int) int {
    sum, maxSum := 0, 0
    for right := 0; right < len(nums); right++ {
        sum += nums[right]
        if right >= k {
            sum -= nums[right-k]
        }
        if right >= k-1 && sum > maxSum {
            maxSum = sum
        }
    }
    return maxSum
}

func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    left, maxLen := 0, 0
    for right := 0; right < len(s); right++ {
        m[s[right]]++
        for m[s[right]] > 1 { // invalid state
            m[s[left]]--
            left++
        }
        if curLen := right - left + 1; curLen > maxLen {
            maxLen = curLen
        }
    }
    return maxLen
}

Add Right
↓
Invalid?
↓
Remove Left
↓
Update Answer

Main Sliding Window Types

┌─────────┐
 2  1  5   1  3  2
└─────────┘
    ┌─────────┐
 2   1  5  1   3  2
    └─────────┘

a b c a b c
↑     ↑
L     R  → [a b c] (Valid ✅)

a b c a b c
↑       ↑
L       R  → [a b c a] (Invalid ❌ → move L until valid: a [b c a])

        EXPAND
L ─────────────→ R

Invalid?
   ↓
Move L →

Valid again?
   ↓
Continue R →

Interview Rules

1. 1. Continuous array/string? → Think Sliding Window
2. 2. Size exactly K? → Fixed Window
3. 3. Longest valid? → Expand + Shrink
4. 4. Smallest valid? → Expand until valid, then shrink
5. 5. Duplicate characters? → Window + Map/Set
6. 6. Character count? → Window + Frequency Map
7. 7. Maximum of every K? → Monotonic Deque
8. 8. Avoid recalculating the full window
9. 9. Left and right usually move only forward
10. 10. Most standard sliding-window solutions are O(n)

Fixed K          → Add right → Remove left → Slide
Longest valid    → Expand right → Invalid? → Shrink left
Substring        → Think window
Duplicates       → Window + Set/Map
Frequency        → Window + Map
Max every K      → Window + Deque

💡 Golden Rule: "Expand with right. Fix the window with left."