🪟 Sliding Window

The Train Window Analogy

Imagine looking out a train window. You see a portion of the landscape - maybe 5 houses at a time. As the train moves:

• A new house enters your view on the right
• An old house exits your view on the left
• Your "window" slides along the landscape

The Sliding Window technique works exactly like this.

Instead of processing every possible group of elements separately, you maintain a "window" that slides across the data, updating as it moves.

Why Sliding Window is So Powerful

The Naive Approach (Slow)

Problem: Find the maximum sum of any 3 consecutive elements.

Array: [2, 1, 5, 1, 3, 2]

Sum of [2,1,5] = 8   (add all 3)
Sum of [1,5,1] = 7   (add all 3 again!)
Sum of [5,1,3] = 9   (add all 3 again!)
Sum of [1,3,2] = 6   (add all 3 again!)

Each sum requires k additions. Total: O(n × k) operations.

The Sliding Window Approach (Fast)

Array: [2, 1, 5, 1, 3, 2]

Initial window [2,1,5]: sum = 8

Slide: remove 2, add 1: sum = 8 - 2 + 1 = 7
Slide: remove 1, add 3: sum = 7 - 1 + 3 = 9  ← Maximum!
Slide: remove 5, add 2: sum = 9 - 5 + 2 = 6

Each slide is just 2 operations (subtract old, add new). Total: O(n) operations!

Two Types of Sliding Windows

Fixed-Size Window

The window size is predetermined (e.g., "any 3 consecutive elements").

Problem: Max sum of k=3 consecutive elements

[2, 1, 5, 1, 3, 2]
 ↓  ↓  ↓           Window size = 3
[2, 1, 5]          sum = 8

    [1, 5, 1]      sum = 7 (8 - 2 + 1)
       [5, 1, 3]   sum = 9 (7 - 1 + 3) ← Maximum
          [1, 3, 2] sum = 6

Variable-Size Window

The window expands or shrinks based on conditions (e.g., "longest substring without repeats").

Problem: Longest substring without repeating characters

String: "abcabcbb"

Start: window = ""
Add 'a': window = "a"         (no duplicates)
Add 'b': window = "ab"        (no duplicates)
Add 'c': window = "abc"       (no duplicates, length 3)
Add 'a': window has 'a'!      SHRINK until no duplicate
         window = "bca"       (length 3)
Add 'b': window has 'b'!      SHRINK
         window = "cab"       (length 3)
...

Maximum length = 3 (windows "abc", "bca", "cab")

The Fixed-Size Window Pattern

How It Works

1. Initialize window with first k elements
2. Record result for first window
3. Slide: remove left element, add right element
4. Update result
5. Repeat until end of array

Common Problems

The Variable-Size Window Pattern

How It Works

1. Start with empty or minimal window
2. EXPAND: Add elements to the right
3. While window VIOLATES constraint:
   - SHRINK: Remove elements from the left
4. Update result
5. Repeat until end of array

Common Problems

When to Use Sliding Window

Often Useful For

• "Find max/min/average of contiguous elements"
• "Find longest/shortest substring/subarray with condition"
• "Check if string contains anagram/permutation"
• "Count subarrays/substrings with property"

Not Suitable For

• Non-contiguous elements (use two pointers or DP)
• When order doesn't matter (use hash maps)
• Problems requiring all pairs/combinations

The Key Signal

"Contiguous subarray" or "substring" in the problem statement is your cue!

Sliding Window vs Other Techniques

How They Differ

"Max sum of k elements"           → Sliding Window
"Two numbers that sum to target"  → Two Pointers
"Sum between index i and j"       → Prefix Sum
"Max sum not taking adjacent"     → Dynamic Programming

Classic Problems Explained

1. Maximum Sum of k Elements

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

Window 1: [2, 3, -1]    sum = 4
Slide:    [3, -1, 6]    sum = 4 - 2 + 6 = 8
Slide:    [-1, 6, 4]    sum = 8 - 3 + 4 = 9
Slide:    [6, 4, 1]     sum = 9 - (-1) + 1 = 11
Slide:    [4, 1, 8]     sum = 11 - 6 + 8 = 13 ← Maximum!

2. Longest Without Repeating Characters

String: "abcdeafb"

a     → window: a         (length 1)
b     → window: ab        (length 2)
c     → window: abc       (length 3)
d     → window: abcd      (length 4)
e     → window: abcde     (length 5)
a     → 'a' exists! shrink until removed
      → window: bcdea     (length 5)
f     → window: bcdeaf    (length 6) ← Maximum!
b     → 'b' exists! shrink
      → window: cdeafb    (length 6)

Answer: 6

3. Minimum Window Containing All Characters

String: "ADOBECODEBANC", need: "ABC"

Expand until window has A, B, C:
window = "ADOBEC" (has A, B, C) → length 6

Shrink while still valid:
window = "DOBEC" → missing A, stop shrinking

Continue expanding and shrinking...
window = "BANC" → length 4 ← Shortest!

Common Mistakes

1. Off-by-One Errors

Window boundaries are tricky. Double-check:

• Do you include or exclude endpoints?
• Is your initial window correct (exactly k elements)?

2. Forgetting to Shrink (Variable Window)

Wrong: Expand but forget to shrink
Result: Window keeps growing, misses constraint

Right: Shrink WHILE constraint is violated

3. Not Handling Empty or Small Inputs

What if the array has fewer than k elements? What if the string is empty?

FAQ

Q: Fixed or variable - how do I know which?

If the problem specifies window size → Fixed. If it asks for longest/shortest satisfying a condition → Variable.

Q: What data structures help sliding window?

• Hash Map: Track frequencies, character counts
• Deque: Track min/max in sliding window efficiently
• Set: Track unique elements

Q: Can I use sliding window on 2D arrays?

Yes! Slide a rectangular window over a matrix. More complex but same principle.

Q: What's the time complexity?

Usually O(n) because each element enters and exits the window at most once.

Summary

Sliding Window maintains a "window" that moves across data, efficiently updating as it slides instead of recalculating everything.

Key Takeaways:

• Fixed window: predetermined size, slides one element at a time
• Variable window: expands and shrinks based on conditions
• Reduces O(n×k) problems to O(n)
• Often useful for contiguous subarray/substring problems
• Key signal: "contiguous" in problem statement
• Track window state with hash maps, sums, or counters
• Watch for off-by-one errors at boundaries

Master sliding window, and a huge category of problems becomes straightforward!