PATTERN 3 OF 22

Sliding Window

Maintain a window of elements in an array or string, expanding and contracting it to find optimal subarrays or substrings in O(n) time.

Time: O(n)

Space: O(1) to O(n)

Learn & Reference

Understanding the Pattern

Sliding Window Pattern

The sliding window pattern transforms brute-force O(n²) nested-loop solutions into elegant O(n) single-pass algorithms. Instead of re-examining every possible subarray from scratch, you maintain a "window" that slides across the data, adding one element on the right and removing one on the left.

Core Concept

A window is defined by two pointers: left and right. You expand the window by moving right forward, and contract it by moving left forward. The key insight is that you never move a pointer backward — this is what guarantees O(n) time.

The 2 Sliding Window Archetypes

1. Variable-Size Window

The window grows and shrinks dynamically based on a condition. Used for "longest/shortest subarray/substring" problems.

Template:

left = 0
for right in range(n):
    add arr[right] to window state
    while window is invalid:
        remove arr[left] from window state
        left += 1
    update answer with current window

Why it works: The right pointer explores every element exactly once. The left pointer only moves forward, also visiting each element at most once. Total work: O(2n) = O(n).

2. Fixed-Size Window

The window always has exactly k elements. Used for "maximum sum of k elements", "average of k elements", and "permutation/anagram in string" problems.

Template:

# Build initial window of size k
for i in range(k):
    add arr[i] to window state

# Slide: add right, remove left
for right in range(k, n):
    add arr[right] to window state
    remove arr[right - k] from window state
    update answer

Why it works: Instead of summing k elements from scratch each time (O(nk)), you add the new element and subtract the old one in O(1) per step.

When Sliding Window Fails

When elements are not contiguous (need dynamic programming or backtracking)
When you need to consider all possible subsets, not just subarrays
When the "window validity" condition is not monotonic (shrinking might make an invalid window valid again)
When the problem requires sorting or random access within the window

Common Mistakes

Forgetting to update state when shrinking: When you move left, you must undo whatever you did when you added that element
Off-by-one in fixed windows: The window [left, right] has size right - left + 1, not right - left
Not handling the empty string/array: Always check for n == 0 edge case
Updating answer at the wrong time: For "minimum" problems, update after shrinking. For "maximum" problems, update after expanding
Using the wrong window type: If the problem says "exactly k" or "of size k", use fixed window. If "longest" or "shortest", use variable window

When to Use

Contiguous subarray or substring

Longest/shortest subarray with condition X

Maximum/minimum sum of k consecutive elements

Find a substring containing all characters of another string

Permutation/anagram of one string in another

Keywords: subarray, substring, contiguous, consecutive, window

Current brute force is O(n²) with nested loops over subarrays

The problem involves a running computation that can be updated incrementally

At most k distinct or at most k replacements

Template

1# --- Variable-Size Window (Longest Valid) ---
2def longest_window(arr):
3    """Find the longest subarray satisfying some condition"""
4    left = 0
5    best = 0
6    state = {}  # or set(), counter, etc.
7
8    for right in range(len(arr)):
9        # Expand: add arr[right] to window state
10        # state.update(...)
11
12        # Shrink: while window is invalid
13        while not valid(state):
14            # Remove arr[left] from state
15            left += 1
16
17        # Update answer
18        best = max(best, right - left + 1)
19
20    return best
21
22# --- Fixed-Size Window ---
23def fixed_window(arr, k):
24    """Process all windows of size k"""
25    # Build first window
26    window = sum(arr[:k])
27    best = window
28
29    # Slide
30    for i in range(k, len(arr)):
31        window += arr[i] - arr[i - k]
32        best = max(best, window)
33
34    return best

{ }

Syntax Reference

1# --- Variable-Size Window ---
2left = 0
3for right in range(len(arr)):
4    # expand: add arr[right] to window
5    window_state.add(arr[right])
6
7    while not is_valid(window_state):
8        # shrink: remove arr[left] from window
9        window_state.remove(arr[left])
10        left += 1
11
12    # update answer (window [left..right] is valid)
13    answer = max(answer, right - left + 1)
14
15# --- Fixed-Size Window ---
16# Build first window
17window_sum = sum(arr[:k])
18best = window_sum
19
20# Slide the window
21for right in range(k, len(arr)):
22    window_sum += arr[right] - arr[right - k]
23    best = max(best, window_sum)

📋

Common Recipes

1# --- Max Profit (Buy & Sell Stock) ---
2def max_profit(prices):
3    min_price = float('inf')
4    max_profit = 0
5    for price in prices:
6        min_price = min(min_price, price)
7        max_profit = max(max_profit, price - min_price)
8    return max_profit
9
10# --- Longest Substring Without Repeats ---
11def length_of_longest_substring(s):
12    char_index = {}
13    left = 0
14    max_len = 0
15    for right in range(len(s)):
16        if s[right] in char_index and char_index[s[right]] >= left:
17            left = char_index[s[right]] + 1
18        char_index[s[right]] = right
19        max_len = max(max_len, right - left + 1)
20    return max_len
21
22# --- Fixed Window: Max Sum of K Elements ---
23def max_sum_k(arr, k):
24    window = sum(arr[:k])
25    best = window
26    for i in range(k, len(arr)):
27        window += arr[i] - arr[i - k]
28        best = max(best, window)
29    return best
30
31# --- Minimum Window Substring ---
32from collections import Counter
33def min_window(s, t):
34    need = Counter(t)
35    have, required = 0, len(need)
36    left = 0
37    result = ""
38    for right in range(len(s)):
39        c = s[right]
40        if c in need:
41            need[c] -= 1
42            if need[c] == 0:
43                have += 1
44        while have == required:
45            window = s[left:right + 1]
46            if not result or len(window) < len(result):
47                result = window
48            if s[left] in need:
49                need[s[left]] += 1
50                if need[s[left]] > 0:
51                    have -= 1
52            left += 1
53    return result

O(n)

Complexity

Operation	Time	Space
Fixed window (sum/avg)	O(n)	O(1)
Longest substring (no repeats)	O(n)	O(min(n, charset))
Minimum window substring	O(n)	O(charset)
Permutation in string	O(n)	O(charset)
Sliding window maximum	O(n)	O(k)

Watch Out

✗When elements are not contiguous (need dynamic programming or backtracking)
✗When you need to consider all possible subsets, not just subarrays
✗When the "window validity" condition is not monotonic (shrinking might make an invalid window valid again)
✗When the problem requires sorting or random access within the window
✗Forgetting to update state when shrinking: When you move `left`, you must undo whatever you did when you added that element
✗Off-by-one in fixed windows: The window `[left, right]` has size `right - left + 1`, not `right - left`
✗Not handling the empty string/array: Always check for `n == 0` edge case
✗Updating answer at the wrong time: For "minimum" problems, update after shrinking. For "maximum" problems, update after expanding
✗Using the wrong window type: If the problem says "exactly k" or "of size k", use fixed window. If "longest" or "shortest", use variable window

PRACTICE PROBLEMS

Two Pointers

Prefix Sums