Sliding Window

The Sliding Window pattern is one of the most powerful techniques for solving contiguous subarray and substring problems. Instead of recalculating everything from scratch for each position, you maintain a "window" that slides through the data, efficiently updating state by adding elements on one side and removing them from the other.

Two Types of Sliding Window:

1. •

   Fixed Size Window: Window size k stays constant. Add right element, process window, remove left element.

2. •

   Variable Size Window: Window expands and contracts based on constraints. Expand right freely, shrink left when constraint violated.

The Key Insight: Both types run in O(n) because each element is added at most once and removed at most once.

When to Use Sliding Window:

• •Problems mentioning "contiguous subarray" or "substring"
• •Finding longest/shortest subarray with a constraint
• •Maximum/minimum sum of k consecutive elements
• •Anagram or permutation finding
• •Character replacement within a limit

Fixed-size sliding window is the simplest form. The window always contains exactly k elements. As the window slides, you add the new right element and remove the old left element.

Template Pattern:

1. •Add element at right pointer to window state
2. •If window has k elements: record result, then remove leftmost element
3. •Move both pointers together

Example: Maximum Sum of K Consecutive Elements Array: [2, 1, 5, 1, 3, 2], k = 3

Window positions:

• •[2, 1, 5] = 8 (sum)
• •[1, 5, 1] = 7
• •[5, 1, 3] = 9 <- Maximum!
• •[1, 3, 2] = 6

Instead of summing k elements each time (O(n*k)), we update incrementally:

• •Add right element: sum += arr[i]
• •Remove left element: sum -= arr[i - k + 1]

This gives us O(n) time complexity.

Watch how the fixed-size window slides through the array, maintaining the sum by adding one element and removing another each step.

Variable-size windows expand and contract based on a constraint. For "longest/maximum" problems, you expand freely and shrink only when the constraint is violated.

Template Pattern:

1. •EXPAND: Add s[right] to window state
2. •SHRINK: While window is invalid, remove s[left] and increment left
3. •UPDATE: Record result AFTER shrinking (window is now valid)

Example: Longest Substring Without Repeating Characters String: "abcabcbb"

• •"a" - valid, length 1
• •"ab" - valid, length 2
• •"abc" - valid, length 3 <- track max
• •"abca" - 'a' repeats! Shrink until valid
• •"bca" - valid, length 3
• •"bcab" - 'b' repeats! Shrink...
• •"cab" - valid, length 3
• •And so on...

Key Insight: Use a Set (or HashMap) to track characters in the current window. When you see a duplicate, shrink from the left until it's removed.

See how the variable-size window expands to include new characters and contracts when duplicates are found.

For "shortest/minimum" problems, the logic flips. You want the smallest valid window, so you record the result INSIDE the while loop (when the window is valid) and keep shrinking to find smaller valid windows.

Template Pattern:

1. •EXPAND: Add element to window
2. •While window is VALID:
   • UPDATE: Record result (inside the loop!)
   • SHRINK: Remove left element and try to find smaller window

Example: Minimum Size Subarray Sum Find shortest subarray with sum >= target Array: [2, 3, 1, 2, 4, 3], target = 7

• •[2, 3, 1, 2] sum=8 >= 7, record length 4, try shrinking
• •[3, 1, 2] sum=6 < 7, not valid, expand
• •[3, 1, 2, 4] sum=10 >= 7, record length 4, shrink
• •[1, 2, 4] sum=7 >= 7, record length 3, shrink
• •[2, 4] sum=6 < 7, expand
• •[2, 4, 3] sum=9 >= 7, record length 3, shrink
• •[4, 3] sum=7 >= 7, record length 2 <- minimum!

Answer: 2

Finding anagrams requires tracking character frequencies. The key optimization is using a "matches" counter instead of comparing entire frequency maps each step.

The Matches Counter Technique:

1. •Build frequency map of pattern
2. •Track how many unique characters have matching frequencies
3. •When matches equals required unique chars, we found an anagram

Example: Find All Anagrams String: "cbaebabacd", Pattern: "abc"

Pattern frequency: {a:1, b:1, c:1}, required = 3 unique chars

Slide fixed window of size 3:

• •"cba": {c:1, b:1, a:1} - matches=3, found at index 0!
• •"bae": {b:1, a:1, e:1} - matches=2
• •"aeb": same
• •"eba": same
• •"bab": {b:2, a:1} - matches=1
• •"aba": {a:2, b:1} - matches=1
• •"bac": {b:1, a:1, c:1} - matches=3, found at index 6!
• •"acd": {a:1, c:1, d:1} - matches=2

Result: [0, 6]

Watch the frequency matching process as the window slides through the string, tracking when all character frequencies match the pattern.

This problem combines variable-size window with a frequency counter. The key insight is that we can replace at most k characters, so the window is valid if:

windowSize - maxFrequency <= k

This means: characters we need to replace <= allowed replacements

Example: "AABABBA", k = 1

• •"A" - maxFreq=1, size=1, replace=0 <= 1, valid, len=1
• •"AA" - maxFreq=2, size=2, replace=0 <= 1, valid, len=2
• •"AAB" - maxFreq=2, size=3, replace=1 <= 1, valid, len=3
• •"AABA" - maxFreq=3, size=4, replace=1 <= 1, valid, len=4 <- max!
• •"AABAB" - maxFreq=3, size=5, replace=2 > 1, shrink!
• •"ABAB" - maxFreq=2, size=4, replace=2 > 1, shrink!
• •"BAB" - maxFreq=2, size=3, replace=1 <= 1, valid
• •And so on...

Optimization: We don't need to decrease maxFreq when shrinking. A larger maxFreq can only help us find longer valid windows, so we only update it when we find a higher frequency.

This is the hardest sliding window problem. Find the minimum window in s that contains all characters of t (including duplicates).

Strategy: Variable size, find minimum, use matches counter.

Example: s = "ADOBECODEBANC", t = "ABC"

We need: {A:1, B:1, C:1}, required = 3 unique chars

Expand until valid, then shrink while staying valid:

• •"ADOBEC" - has A, B, C - valid! length=6, try shrinking
• •"DOBEC" - missing A - invalid, expand
• •"DOBECODEBA" - valid again, length=10
• •Keep shrinking: "CODEBA" (6), "ODEBA" invalid...
• •Eventually find "BANC" - length=4, this is minimum!

Key Difference from Find Anagrams:

• •Window size is variable (not fixed at pattern length)
• •We shrink WHILE valid to find minimum
• •Track the actual substring, not just starting indices

Problem: Given binary array and k, return max consecutive 1s if you can flip at most k 0s.

Reframe: Find longest subarray with at most k zeros.

Example: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

Key Insight: We're not actually flipping anything. We're just finding the longest window with at most k zeros.

Problem: Collect maximum fruits using 2 baskets. Each basket holds one type. Must pick consecutive trees.

Translation: Find longest subarray with at most 2 distinct elements.

This generalizes to at most K distinct elements.

Example: fruits = [1,2,1,2,3], k=2

Key Insight: Track frequency map size. When size > k, shrink until we remove a fruit type entirely (frequency becomes 0).

Problem: Count subarrays with exactly K distinct integers.

Challenge: "Exactly K" is hard to track directly with sliding window.

Brilliant Trick: exactlyK = atMostK(K) - atMostK(K-1)

Why This Works:

• •atMostK(K) counts all subarrays with 1, 2, ..., K distinct elements
• •atMostK(K-1) counts all subarrays with 1, 2, ..., K-1 distinct elements
• •Subtracting gives exactly those with K distinct

Example: nums = [1,2,1,2,3], K=2

atMostK(2) counts: [1], [1,2], [2], [2,1], [1,2,1], [1], [1,2], [2], [2,3], [3], ... atMostK(1) counts: [1], [2], [1], [2], [3], ... exactly(2) = difference

Implementation: Run atMostK twice, subtract results.

Problem: Given array and window size k, return max element in each window position.

Naive: O(n*k) - check all k elements each position. Optimal: O(n) - use monotonic deque!

Monotonic Deque Strategy:

• •Maintain deque of indices in DECREASING order of values
• •Front of deque is always the maximum
• •When adding new element, remove smaller elements from back
• •When sliding, remove front if it's outside window

Example: nums = [1,3,-1,-3,5,3,6,7], k = 3

Problem: Check if s2 contains a permutation of s1.

Translation: Does any substring of s2 have the same character frequencies as s1?

Approach: Fixed-size window (size = s1.length), track matching frequencies.

Optimization: Instead of comparing entire maps, use matches counter.

Example: s1 = "ab", s2 = "eidbaooo"

Target: {a:1, b:1}

Key Insight: This is the same as "Find All Anagrams" but returns boolean on first match.

Edge Cases to Handle:

1. Empty Input

2. Window Larger Than Array

3. No Valid Window Exists

4. Single Element

5. All Same Elements

Common Mistakes:

Fixed vs Variable Window Decision Tree:

Problem Pattern Quick Reference:

Data Structure Selection:

Time Complexity: O(n)

Despite nested loops (for + while), sliding window is O(n) because:

• •Each element is added to window at most once (right pointer)
• •Each element is removed from window at most once (left pointer)
• •Total operations = 2n = O(n)

Space Complexity:

• •Fixed window (no map): O(1)
• •With HashMap: O(k) where k is the size of the character set
  • For lowercase letters: O(26) = O(1)
  • For all ASCII: O(128) = O(1)
  • For Unicode: O(k) where k is unique characters
• •Monotonic deque: O(k) where k is window size

Problem-Specific Complexity:

Why Sliding Window Works: The key insight is that we never "go back." Both left and right pointers only move forward. This monotonic property guarantees linear time.

Common Optimizations:

1. •Use array instead of HashMap for fixed alphabets
2. •Track maxFrequency without recalculating
3. •Jump left pointer directly using lastSeen map

Fixed Size Window Template:

Variable Size - Maximum:

Variable Size - Minimum:

Exactly K Trick:

Interview Tips:

• •Draw the window as you walk through examples
• •Always clarify: max or min? fixed or variable?
• •For frequency problems, consider matches counter
• •Remember: update location differs for max vs min