vault

Sliding Window

18 min read

Sliding Window

The sliding-window technique maintains a contiguous window (a subarray or substring) defined by two indices that walk rightward through the input. Instead of recomputing a property over the window from scratch each time it shifts (which costs O(window size) per shift, giving O(n × window) overall — typically O(n²)), you update the property incrementally: add the new element entering on the right, subtract the old element leaving on the left, and the window’s invariant is maintained in O(1) per shift. Total cost: O(n). The pattern comes in two flavors — fixed-size windows (the window’s width is a constant k) and variable-size windows (the window grows and shrinks based on a predicate). The variable-size case is the workhorse of “longest/shortest substring with property X” problems.

1. Intuition — Looking Through a Train Window

Picture sitting on a moving train, looking out a fixed-size rectangular window at the landscape rolling past. At any moment you see a slice of the world. As the train moves forward, a new sliver of countryside enters the window’s right edge while an equal sliver of already-seen countryside disappears off the left edge. You don’t have to re-look at everything — you just track the new sliver coming in and the old sliver going out.

If you’re counting, say, cows visible through the window: as the train advances one car-length, you add the cows newly visible on the right and subtract the cows that just slid past on the left. Your count is always current, updated in O(1) per shift, never re-scanning the entire window.

That’s a fixed-size sliding window. The variable-size version is like an accordion window that opens wider when you want to capture more landscape and contracts when something objectionable (a billboard, a power line) is in view that you want to push out the left edge.

The deep reason this pattern works at all: the property being tracked must be incrementally maintainable — adding/removing an element on the boundary should change the property in O(1) (or at worst O(log n) using a heap/hash-counter). If recomputing requires touching the whole window (e.g., median, since deletion from the middle is hard), naive sliding window degrades, and you need an auxiliary data structure or a different approach.

2. Tiny Worked Example — Max Sum of Subarray of Size k = 3

Given arr = [2, 1, 5, 1, 3, 2] and k = 3, find the maximum sum of any contiguous subarray of length 3.

Naive O(n × k): for each of the n - k + 1 = 4 starting positions, sum 3 elements. 12 additions.

Sliding window O(n):

StepwindowsumbestAction
init[2, 1, 5]88initial sum of first 3
1[1, 5, 1]8 + 1 − 2 = 78add arr[3]=1, drop arr[0]=2
2[5, 1, 3]7 + 3 − 1 = 99add arr[4]=3, drop arr[1]=1
3[1, 3, 2]9 + 2 − 5 = 69add arr[5]=2, drop arr[2]=5

Total: 3 + 1 + 1 + 1 = 6 additions/subtractions. The + new − old update is the entire idea. For n = 10⁶ and k = 10³, this drops 10⁹ ops to ~2 × 10⁶ — three orders of magnitude.

3. The Pattern Recognition Signal

Reach for sliding window when any of the following appear:

  1. “Longest/shortest contiguous subarray (or substring) such that …” — variable-size window. The ”…” is your predicate.
  2. “Maximum/minimum sum (or product, or count) of a subarray of size k” — fixed-size window.
  3. “Number of substrings/subarrays satisfying property P” — variable-size window with counting (often involves the trick “for each right, count valid lefts ending here”).
  4. “Subarray with sum equal to S” — variable-size, but only when all elements are non-negative (then the predicate is monotone in window length). With negatives, sliding window breaks; use Prefix Sums + Hash Table instead.
  5. “At most K distinct characters/elements” — variable-size, Hash Table inside the window.
  6. “Longest substring with all unique characters” — variable-size.
  7. “Permutation/anagram in a string” — fixed-size with a frequency-counter hash.
  8. “Window of size k, sliding” explicitly named in the problem (e.g., max in sliding window, LC 239).

The inverse signals — when sliding window is the wrong tool:

  • The subarrays of interest are not contiguous (e.g., subsequences). Use Dynamic Programming instead.
  • The predicate is not monotone with window length, and element values can be negative or otherwise non-monotone. The window’s “shrink left when predicate fails” rule depends on the predicate becoming satisfiable again as the window contracts; if it doesn’t, the algorithm misses solutions.
  • You need every window’s value globally, not just the optimum (then you may need an auxiliary structure like a Monotonic Deque for sliding-window maximum, LC 239).

4. Pseudocode

4.1 Fixed-Size Window of Width k

fixed_window(arr, k):
    if length(arr) < k: return INVALID
    window_sum := sum(arr[0..k-1])           # initial window
    best := window_sum
    for right in k .. length(arr) - 1:
        window_sum := window_sum + arr[right] - arr[right - k]
        best := max(best, window_sum)
    return best

The invariant: at the top of every loop iteration, window_sum equals the sum of arr[right - k .. right - 1]. After the line that adds arr[right] and subtracts arr[right - k], the invariant is shifted forward by one and window_sum equals arr[right - k + 1 .. right].

4.2 Variable-Size Window — Longest Subarray with Property

variable_window(arr, predicate):
    left := 0
    best := 0
    state := empty                            # whatever the predicate needs
    for right in 0 .. length(arr) - 1:
        state := add(state, arr[right])       # extend window by one on the right
        while not predicate(state):
            state := remove(state, arr[left]) # contract window on the left
            left := left + 1
        best := max(best, right - left + 1)   # current window is valid
    return best

The structure is: expand right unconditionally; contract left while the window is invalid; record the answer once it’s valid again. Each index is added and removed at most once, so even though there’s a nested while, the total work is O(n) amortized — a classic “two pointers same-direction” complexity argument.

4.3 Variable-Size Window — Shortest Subarray with Property

For the shortest version, the contract loop goes the other way: as long as the predicate is satisfied, try to shrink from the left and record the (potentially smaller) answer.

shortest_window(arr, predicate):
    left := 0
    best := INFINITY
    state := empty
    for right in 0 .. length(arr) - 1:
        state := add(state, arr[right])
        while predicate(state):               # try to shrink
            best := min(best, right - left + 1)
            state := remove(state, arr[left])
            left := left + 1
    return (INFINITY if best == INFINITY else best)

4.4 Decision Tree — Fixed vs Variable

Does the problem specify a window size k?
├─ YES → fixed-size window. Initialize sum/state over first k, then slide.
└─ NO  → variable-size window.
         Asking for longest? → expand always, contract while invalid.
         Asking for shortest? → expand always, shrink while valid.
         Asking for count of windows? → for each `right`, count valid `left`s.

5. Python Implementation

5.1 Fixed-Size: Maximum Sum of k-Length Subarray

def max_sum_k(arr: list[int], k: int) -> int:
    if len(arr) < k:
        raise ValueError("array shorter than k")
    window = sum(arr[:k])
    best = window
    for right in range(k, len(arr)):
        window += arr[right] - arr[right - k]
        best = max(best, window)
    return best

5.2 Variable-Size: Longest Substring Without Repeating Characters (LC 3)

def length_of_longest_substring(s: str) -> int:
    last_seen = {}                             # char -> last index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1           # jump left past prior occurrence
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

The left = last_seen[ch] + 1 jump is an optimization over the textbook contract-one-at-a-time loop — when we know exactly where the duplicate was, we can skip the entire prefix in one move. The amortized work argument still holds: left only ever advances rightward.

5.3 Variable-Size Shortest: Minimum Window Substring (LC 76)

Find the shortest substring of s that contains every character of t (with multiplicity). The canonical hard sliding-window problem.

from collections import Counter
 
def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""
    need = Counter(t)
    have = {}                                   # window's char counts
    needed_distinct = len(need)
    formed = 0                                  # how many distinct chars have hit their target count
    left = 0
    best = (float("inf"), 0, 0)                 # (length, l, r)
    for right, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            formed += 1
        while formed == needed_distinct:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            ch_left = s[left]
            have[ch_left] -= 1
            if ch_left in need and have[ch_left] < need[ch_left]:
                formed -= 1
            left += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

The formed/needed_distinct accounting is the key trick: instead of comparing the entire have dict against need on every iteration (which would be O(|alphabet|) per step), we maintain a single integer that tells us at a glance whether the window currently meets the requirement. This brings the per-step cost to O(1) amortized.

5.4 Fixed-Size: Fruit Into Baskets (LC 904)

You walk through a row of fruit trees; you have two baskets, each holds one fruit type, unlimited quantity. Pick the longest run of consecutive trees whose fruits fit in the two baskets — i.e., the longest subarray with at most 2 distinct values.

from collections import defaultdict
 
def total_fruit(fruits: list[int]) -> int:
    count = defaultdict(int)
    left = 0
    best = 0
    for right, f in enumerate(fruits):
        count[f] += 1
        while len(count) > 2:
            count[fruits[left]] -= 1
            if count[fruits[left]] == 0:
                del count[fruits[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

This generalizes to “longest subarray with at most K distinct” (LC 340) by replacing 2 with K. The pattern is so common it’s worth recognizing on sight.

5.5 Permutation in String (LC 567) — Fixed-Size with Frequency Hash

Check if any permutation of t is a substring of s. Window size = len(t), slide it across s, compare frequency counts.

def check_inclusion(t: str, s: str) -> bool:
    if len(t) > len(s):
        return False
    need = [0] * 26
    have = [0] * 26
    for ch in t:
        need[ord(ch) - 97] += 1
    for i in range(len(t)):
        have[ord(s[i]) - 97] += 1
    matches = sum(1 for i in range(26) if have[i] == need[i])
    if matches == 26:
        return True
    for right in range(len(t), len(s)):
        new_idx = ord(s[right]) - 97
        old_idx = ord(s[right - len(t)]) - 97
        # update new
        if have[new_idx] == need[new_idx]:
            matches -= 1
        have[new_idx] += 1
        if have[new_idx] == need[new_idx]:
            matches += 1
        # update old
        if have[old_idx] == need[old_idx]:
            matches -= 1
        have[old_idx] -= 1
        if have[old_idx] == need[old_idx]:
            matches += 1
        if matches == 26:
            return True
    return False

The 26-letter array is faster than a hash table for fixed alphabets. The matches counter tracks how many letters currently have the right count, an O(1) check instead of a 26-element comparison every step.

6. Complexity

Time: O(n). The right pointer makes exactly n advances. The left pointer also makes at most n advances total (it only moves rightward and never backward). Even though the left-advance is inside a nested while loop, the total number of left-advances across the entire run is bounded by n, so the amortized cost per outer iteration is O(1). Inner work per pointer move is O(1) for sums, O(1) amortized for hash-counter updates, O(log n) if you use a sorted structure.

Space: O(1) for sums and arithmetic windows; O(k) or O(|alphabet|) for hash-counter windows. No copies of the window’s content — only the running aggregate.

Why this beats brute force. Brute force enumerates all O(n²) contiguous substrings/subarrays and checks each, which costs O(n²) at best (with the predicate evaluated incrementally) and O(n³) at worst. Sliding window achieves O(n) by amortizing: each element enters and leaves the window exactly once, so the total work across the entire run is 2n × O(per-element cost). For n = 10⁵ and a check that’s even O(n) brute, sliding window goes from ~10¹⁰ (untimely) to ~10⁵ (instant).

The amortized argument is the deepest part. A naive look at the algorithm — outer for-loop containing an inner while-loop — suggests O(n²). The correct argument requires noting that the inner loop’s total iteration count, summed across all outer iterations, is bounded by n (because left is monotone). This is the same argument used for the Two Pointers same-direction pattern (which sliding window is, with extra window-state semantics).

7. Variants and Sub-patterns

7.1 Sliding Window Maximum (LC 239) — Auxiliary Monotonic Deque

For each window of fixed size k, output the maximum. The naive “scan each window” is O(nk). The clever solution maintains a deque of indices whose values are strictly decreasing from front to back; when a new element enters, pop all smaller indices from the back; when the front index falls out of the window, pop it from the front. The deque’s front is always the current window’s max. Each index is pushed and popped at most once → amortized O(n).

from collections import deque
 
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()
    res = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()                       # drop indices outside the window
        while dq and nums[dq[-1]] < x:
            dq.pop()                            # maintain decreasing invariant
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

The deque is the auxiliary structure required because removing the middle element from the window is hard (and max doesn’t support incremental removal). The monotonic invariant guarantees the front is always valid.

7.2 Counting-Subarrays Trick

For “number of subarrays with at most K distinct elements,” sliding window finds the count directly. For “number of subarrays with exactly K distinct,” compute atMost(K) − atMost(K - 1). This atMost-difference trick is a recurring pattern (LC 992, LC 1248).

7.3 Negative Numbers Break Naive Sliding Window for Sum-Equals-K

If the array can contain negatives and you want subarrays summing to k, you cannot use sliding window: shrinking the left pointer when sum exceeds k might be wrong because future negative elements could pull the sum back down. Use Prefix Sums + Hash Table instead (LC 560). The lesson: sliding window’s contract-when-invalid rule requires the property to be monotone in window length given the elements at hand.

7.4 Sliding Window on a String of Bits — Bit Tricks

For binary or small-alphabet windows, you can sometimes encode the window’s state as a single integer (bitmask) and detect repeated states with a hash set. Used in LC 187 (repeated DNA sequences).

7.5 Two-Window Variant

Some problems require maintaining two adjacent or overlapping windows simultaneously: e.g., LC 1234 “Replace the Substring for Balanced String.” The structure is the same, just doubled bookkeeping.

7.6 Sliding Window on Sorted Frequency

When the predicate is “max element minus min element ≤ K” (LC 1438 absolute-diff constraint), you need a structure that supports O(log n) insert, remove, and min/max — a sorted multiset (SortedList in Python, TreeMap in Java). The sliding window structure remains, but the per-step cost is O(log n), giving O(n log n) overall.

8. Pitfalls

8.1 Off-By-One on the Initial Window

For fixed-size windows, the initial sum covers arr[0..k-1]. After the loop’s first iteration with right = k, the window should cover arr[1..k]. Don’t accidentally double-count the boundary or skip an element. Trace by hand on n = 4, k = 2.

8.2 Inner while vs if

For longest-subarray problems where the predicate can fail by more than one (e.g., adding a new element creates 2 duplicates simultaneously — impossible for set-uniqueness, but possible for “at most K distinct” if the alphabet is small), you must use a while to keep contracting until the invariant is restored, not a single if. An if works only when the worst-case violation requires exactly one shrink.

8.3 Forgetting to Update the Answer After Contracting

In some variable-size problems, the answer must be updated only when the window is valid. After contracting, check whether you’re still valid, then update. In the longest-window pattern, the contraction restores validity, so the post-contract best = max(best, right - left + 1) is always correct. In the shortest-window pattern, the answer is updated inside the while (since the window is valid throughout the contraction).

8.4 Hash-Counter Stale Keys

When using defaultdict(int) for character counts, a key whose count drops to 0 still exists in the dict — calling len(count) then over-counts distinct characters. Either explicitly del count[ch] when it reaches 0, or use sum(1 for v in count.values() if v > 0).

8.5 Using Sliding Window When the Predicate Is Non-Monotone

For “longest subarray summing to exactly K” with arbitrary integers, sliding window fails. The contract rule “shrink left while sum > K” is wrong because adding future negatives could bring the sum back. Detect this trap: can the property be temporarily violated and then become valid again with future additions, without contracting? If yes, sliding window doesn’t apply. Use prefix sums + hash map.

8.6 Confusing Subarray with Subsequence

Sliding window operates on contiguous subarrays/substrings. If the problem says “subsequence” (elements may be non-contiguous), sliding window is the wrong tool — that’s Dynamic Programming territory.

8.7 Initial Best for Shortest

For shortest-window problems, initialize best = float('inf') and check at the end whether it’s still infinite (meaning no valid window exists). Returning a stale 0 is a common bug.

9. Diagram — The Variable-Size Window in Action

flowchart TD
    S0["[a, b, c, a, b, c, b, b]\n         left=0   right=0\n      window: [a]"] --> S1["         left=0   right=1\n      window: [a, b]"]
    S1 --> S2["         left=0   right=2\n      window: [a, b, c]"]
    S2 -->|"add 'a' duplicates 'a'"| S3["         left=1   right=3\n      window: [b, c, a]"]
    S3 -->|"add 'b' duplicates 'b'"| S4["         left=2   right=4\n      window: [c, a, b]"]
    S4 -->|"add 'c' duplicates 'c'"| S5["         left=3   right=5\n      window: [a, b, c]"]
    S5 -->|"add 'b' duplicates 'b'"| S6["         left=5   right=6\n      window: [c, b]"]
    S6 -->|"add 'b' duplicates 'b'"| S7["         left=7   right=7\n      window: [b]"]

What this diagram shows. The longest-substring-without-repeating-characters algorithm walking through "abcabcbb". Each box shows the window’s contents, the values of left and right, and (on the arrows) what triggered the next state transition. Notice that right advances by one on every step (the unconditional outer-loop step), while left jumps forward only when the new element introduces a duplicate within the current window. The longest valid window seen here is [a, b, c] with length 3, which appears multiple times. The total number of right advances is n = 8; the total number of left advances is also at most n — that’s the amortized O(n) argument made visual.

10. Common Interview Problems

#ProblemWindow TypeKey Trick
LC 3Longest Substring Without RepeatingVariableHash of last-index; jump left
LC 76Minimum Window SubstringVariable shortestformed counter
LC 30Substring with Concatenation of All WordsVariable, multi-wordHash of word counts
LC 159Longest Substring with At Most 2 DistinctVariableHash counter
LC 340Longest Substring with At Most K DistinctVariableHash counter
LC 904Fruit Into BasketsVariable (≤2 distinct)Same as LC 159
LC 209Minimum Size Subarray SumVariable shortestNon-negatives only
LC 643Maximum Average Subarray IFixedTrivial sliding sum
LC 1456Max Vowels in Substring of Length KFixedCount vowel deltas
LC 567Permutation in StringFixedChar freq compare
LC 438Find All Anagrams in a StringFixedSame as LC 567, collect indices
LC 239Sliding Window MaximumFixed + monotonic dequeAux structure
LC 480Sliding Window MedianFixed + two heapsAux structure
LC 992Subarrays with K Different IntegersVariable, countatMost(K) − atMost(K−1)
LC 1004Max Consecutive Ones IIIVariableAllow ≤K zeros
LC 424Longest Repeating Character ReplacementVariablewindow − maxFreq ≤ k
LC 1208Get Equal Substrings Within BudgetVariableCost-bounded
LC 1248Count Number of Nice SubarraysVariable, countatMost diff
LC 1493Longest Subarray of 1s After DeletingVariableAt most 1 zero
LC 1695Maximum Erasure ValueVariableDistinct-elements window
LC 1838Frequency of Most Frequent ElementVariable + sortCost = (k×nums[r]) − sum
LC 187Repeated DNA SequencesFixed + hashBitmask trick possible

11. Open Questions

  • Is there a precise theorem characterizing which predicates admit a sliding-window solution? Conjecture: predicates that are prefix-closed under contraction — i.e., if a window is invalid, the only way to restore validity is to shrink from the left.
  • How does “sliding window over a stream” (no random access) generalize the array case? The TCP sliding-window protocol is a real-world instance — same name, very different mechanics.
  • When does the auxiliary-data-structure version (heap, monotonic deque, sorted multiset) beat alternatives like segment trees for sliding-window aggregate queries?

12. See Also

Graph View

Backlinks