Sliding Window

Quick Revisit

• USE WHEN: Longest/shortest/max-sum contiguous subarray with a constraint, or fixed-size window aggregation
• INVARIANT: Left pointer never moves backward; window state is updated incrementally in O(1) per step
• TIME: O(n) | SPACE: O(1) to O(k) depending on window state
• CLASSIC BUG: Forgetting to shrink the window (advance left pointer) when constraint is violated
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Difficulty: Beginner | Prerequisites: Two Pointers | CF Rating: 1100–1500

Process contiguous subarrays or substrings in $O(n)$ by maintaining a window that slides across the input—adding one element on the right and removing another on the left instead of recomputing from scratch each time. A sliding window is a two-pointer in disguise, but with a crucial twist: the left pointer never moves backward. That "monotone advance" is what guarantees $O(n)$ total work despite the inner while loop. The fingerprint to burn into memory: "longest/shortest subarray with [constraint]" where all elements are non-negative—the moment you see that shape, reach for this technique. A useful mnemonic for the four-step loop: EARS—Expand right, Adjust (contract) left, Record answer, Slide forward.

The technique traces its roots to network flow control (TCP's sliding window protocol, 1974), then surfaced in algorithm design through the Rabin-Karp rolling hash (1987)—essentially a fixed-size sliding window over a string. The monotonic deque trick for window max/min came later, formalizing the $O(n)$ solution to a problem that otherwise requires $O(n\log k)$ with a heap.

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading
• Code Reading Exercise
• What to Solve Next

---

Intuition

Start with an array of eight elements. You need the maximum sum of any contiguous subarray of size $k=3$:

a = [2, 1, 5, 1, 3, 2, 4, 1]
     0  1  2  3  4  5  6  7

Your first instinct: loop over every starting position, sum up $k$ elements, track the maximum.

Window [0..2]: 2 + 1 + 5 = 8     (3 additions)
Window [1..3]: 1 + 5 + 1 = 7     (3 additions)
Window [2..4]: 5 + 1 + 3 = 9     (3 additions)
Window [3..5]: 1 + 3 + 2 = 6     (3 additions)
Window [4..6]: 3 + 2 + 4 = 9     (3 additions)
Window [5..7]: 2 + 4 + 1 = 7     (3 additions)
                                  -----------
                           Total: 18 additions

Six windows times three additions each $=18$ operations. In general, $(n-k+1)\cdot k$ operations—$O(n\cdot k)$.

Now imagine $n={10}^5$ and $k=5\cdot {10}^4$. That is $\approx 2.5\cdot {10}^9$ operations. TLE guaranteed.

Look at the repeated work. Windows [0..2] and [1..3] share two elements (1 and 5). You summed them both times. Every consecutive pair of windows overlaps in $k-1$ elements, and you recompute that shared sum from scratch every time.

Window [0..2]:  [ 2   1   5 ] .   .   .   .   .
Window [1..3]:    .  [ 1   5   1 ] .   .   .   .
                      ^^^^^^^
                shared: 2 of 3 elements recomputed

We are re-adding $k-1$ elements for every single step. There has to be a better way.

When the window slides right by one position, you only need to add the new element entering on the right and subtract the old element leaving on the left—one addition and one subtraction instead of $k$ additions.

Think of a caterpillar crawling along a branch. Its body covers a fixed length at all times. When it moves forward one step, the front extends to grip new bark while the rear releases—the middle of the body stays put.

Before slide:     =====[#####]===========
                        ^^^^^
                     caterpillar body (k cells)

After one step:   ======[#####]==========
                   drop ^     ^ grab
                   rear       new front

This analogy holds for fixed-size windows. It breaks for variable-size windows, where the caterpillar can also stretch or compress its body—that variant needs a different mental model (the expand/shrink pattern):

while r < n:
    expand: add a[r] to window state
    r++
    while window violates constraint:
        shrink: remove a[l] from window state
        l++
    update answer from current window

The variable-size version works in $O(n)$ because each element enters and leaves the window at most once—both $l$ and $r$ only move right.

Visual Walkthrough

Same array, $k=3$. Compute the first window's sum directly, then slide.

a = [2, 1, 5, 1, 3, 2, 4, 1]
     0  1  2  3  4  5  6  7

Step 0: Initialize—sum the first window directly

  +---+---+---+---+---+---+---+---+
  | 2 | 1 | 5 | 1 | 3 | 2 | 4 | 1 |
  +---+---+---+---+---+---+---+---+
  [***********]
  sum = 2 + 1 + 5 = 8                ops used: 2 adds
  best = 8

Step 1: Slide right—drop a[0]=2, add a[3]=1

  +---+---+---+---+---+---+---+---+
  | 2 | 1 | 5 | 1 | 3 | 2 | 4 | 1 |
  +---+---+---+---+---+---+---+---+
   -2  [***********]  +1
  sum = 8 - 2 + 1 = 7                ops used: 1 add, 1 sub
  best = 8

Step 2: Slide right—drop a[1]=1, add a[4]=3

  +---+---+---+---+---+---+---+---+
  | 2 | 1 | 5 | 1 | 3 | 2 | 4 | 1 |
  +---+---+---+---+---+---+---+---+
       -1  [***********]  +3
  sum = 7 - 1 + 3 = 9                ops used: 1 add, 1 sub
  best = 9  <-- new best

Step 3: Slide right—drop a[2]=5, add a[5]=2

  +---+---+---+---+---+---+---+---+
  | 2 | 1 | 5 | 1 | 3 | 2 | 4 | 1 |
  +---+---+---+---+---+---+---+---+
           -5  [***********]  +2
  sum = 9 - 5 + 2 = 6                ops used: 1 add, 1 sub
  best = 9

Step 4: Slide right—drop a[3]=1, add a[6]=4

  +---+---+---+---+---+---+---+---+
  | 2 | 1 | 5 | 1 | 3 | 2 | 4 | 1 |
  +---+---+---+---+---+---+---+---+
               -1  [***********]  +4
  sum = 6 - 1 + 4 = 9                ops used: 1 add, 1 sub
  best = 9  (tied)

Step 5: Slide right—drop a[4]=3, add a[7]=1

  +---+---+---+---+---+---+---+---+
  | 2 | 1 | 5 | 1 | 3 | 2 | 4 | 1 |
  +---+---+---+---+---+---+---+---+
                   -3  [***********]  +1
  sum = 9 - 3 + 1 = 7                ops used: 1 add, 1 sub
  best = 9

Answer: 9 (windows [2..4] and [4..6] both sum to 9).

Operation count:

Brute force:  6 windows x 3 additions each  = 18 operations
Sliding:      2 (initial) + 5 x 2 (slides)  = 12 operations

Savings grow with k:
  n=100, k=50:  brute = 2550 ops,  sliding = 148 ops   (17x faster)
  n=10^5, k=5*10^4:  brute ~ 2.5*10^9,  sliding ~ 2*10^5

The same savings apply to variable-size windows. Here is a walkthrough of "longest substring with at most 2 distinct characters" on "abacbca":

String: "a b a c b c a"
         0 1 2 3 4 5 6

--- r expands right, l shrinks when distinct > 2 ---

r=0: [a]             distinct={a:1}         len=1
     l
     r

r=1: [a,b]           distinct={a:1,b:1}     len=2
     l
        r

r=2: [a,b,a]         distinct={a:2,b:1}     len=3  <-- best so far
     l
           r

r=3: [a,b,a,c]       distinct={a:2,b:1,c:1} = 3 > 2  VIOLATION!
     l
              r
     shrink l:
       l=1: remove a -> {a:1,b:1,c:1} = 3   still bad
       l=2: remove b -> {a:1,c:1} = 2        OK!
              [a,c]   len=2
              l
              r

r=4: [a,c,b]         distinct={a:1,c:1,b:1} = 3 > 2  VIOLATION!
              l
                 r
     shrink l:
       l=3: remove a -> {c:1,b:1} = 2        OK!
              [c,b]   len=2
                 l
                 r

r=5: [c,b,c]         distinct={c:2,b:1}     len=3  <-- ties best
                 l
                    r

r=6: [c,b,c,a]       distinct={c:2,b:1,a:1} = 3 > 2  VIOLATION!
                 l
                       r
     shrink l:
       l=4: remove c -> {c:1,b:1,a:1} = 3   still bad
       l=5: remove b -> {c:1,a:1} = 2        OK!
                    [c,a] len=2
                       l
                       r

Answer: 3  (substrings "aba" or "cbc")

Window Expansion/Contraction—Step by Step

Detailed trace for a variable window on a numeric array: longest subarray with sum ≤ 7, on [2, 1, 3, 1, 1, 2].

Step 1: Expand R
  [2, 1, 3, 1, 1, 2]
   L
   R
   sum=2 <=7  window=[2] len=1

Step 2: Expand R
  [2, 1, 3, 1, 1, 2]
   L  R
   sum=3 <=7  window=[2,1] len=2

Step 3: Expand R
  [2, 1, 3, 1, 1, 2]
   L     R
   sum=6 <=7  window=[2,1,3] len=3

Step 4: Expand R
  [2, 1, 3, 1, 1, 2]
   L        R
   sum=7 <=7  window=[2,1,3,1] len=4

Step 5: Expand R
  [2, 1, 3, 1, 1, 2]
   L           R
   sum=8 >7!  CONTRACT -->

Step 6: Contract L
  [2, 1, 3, 1, 1, 2]
      L        R
   sum=6 <=7  window=[1,3,1,1] len=4

Step 7: Expand R
  [2, 1, 3, 1, 1, 2]
      L           R
   sum=8 >7!  CONTRACT -->

Step 8: Contract L
  [2, 1, 3, 1, 1, 2]
         L        R
   sum=7 <=7  window=[3,1,1,2] len=4

Answer: max length = 4

Each element enters the window exactly once (when R advances) and leaves at most once (when L advances). Total pointer movements: R moves 6 times, L moves 2 times—8 operations for a 6-element array, well within $O(2n)$.

Why both pointers only move right—amortized $O(n)$:

    l moves -->           r moves -->
    0  1  2  3  4  5  6  7  8  9
    +--+--+--+--+--+--+--+--+--+
    |  |  |  |  |  |  |  |  |  |
    +--+--+--+--+--+--+--+--+--+

    r advances n times total    ---> n operations
    l advances at most n times  ---> n operations
                                     ----------
                           Total:    O(2n) = O(n)

The Invariant

Fixed-size window:

+------------------------------------------------------------------+
| INVARIANT: The window always contains exactly k consecutive       |
| elements a[i-k+1 .. i]. The running variable `sum` is always     |
| equal to a[i-k+1] + a[i-k+2] + ... + a[i].                      |
|                                                                   |
| Maintained by: each slide subtracts the element leaving the left  |
| edge and adds the element entering the right edge.                |
+------------------------------------------------------------------+

Established in Step 0 (direct sum of the first $k$ elements) and preserved by every subsequent slide.

Verify it with Step 3: $sum=9$ before the slide, representing window [2..4] with elements $5+1+3=9$. Subtract $a[2]=5$ (leaving the left) and add $a[5]=2$ (entering the right). The new sum $6$ equals $1+3+2$—exactly window [3..5]. Invariant holds.

If you forget to subtract the leaving element, sum accumulates and the invariant breaks. That is the most common bug—see Gotchas.

Variable-size window:

+------------------------------------------------------------------+
| INVARIANT: The window [l, r) always satisfies the constraint.     |
| When r advances and the constraint breaks, l advances until the   |
| constraint is restored. Both l and r only move right, so each     |
| element enters and leaves the window at most once: O(n) total.    |
+------------------------------------------------------------------+

The key requirement is monotonicity: expanding the window can only make the constraint worse (e.g., sum only increases when all elements are non-negative). If expanding could both break and restore the constraint, the two-pointer approach fails.

The inner shrink must use while, not if. One expansion can cause multiple violations that need multiple shrinks. In the walkthrough above, at $r=3$ we had to shrink twice (from $l=0$ to $l=2$) before the constraint was restored.

What the Code Won't Teach You

The hardest part is recognition, not implementation. The template is eight lines. The real skill is reading a problem statement and seeing that the answer lives in a contiguous subarray whose validity is monotonic. Train the instinct by asking: "If I expand the window and it becomes invalid, can I always fix it by shrinking from the left?"

Monotonicity is the gatekeeper. If expanding the window can both break and restore the constraint, sliding window is wrong. This rules out sums with negative numbers, XOR-based conditions, and any property where removing an element from the left can make things worse.

  MONOTONICITY CHECK -- CAN I USE SLIDING WINDOW?
  ================================================

  Expanding the window (adding element on right):
    Can only make constraint WORSE?
       |
       +-- YES -->  Monotonic [yes]  -> Sliding window works
       |             (e.g., sum of non-negatives only grows)
       |
       +-- NO  -->  Non-monotonic [no]  -> Use prefix sums + hash map,
                     (e.g., sum with negatives       or binary search,
                      can grow or shrink)             or segment tree

The technique generalizes beyond arrays. Sliding window applies to circular arrays (modular indexing or duplicate the array), strings (frequency maps), and even tree BFS frontiers. The core idea—maintain a "window" cheaply as you expand/contract—is more general than the array setting.

When to Reach for This

Trigger phrases—when you see these in a problem statement, think sliding window:

• "maximum/minimum sum over all subarrays of size $k$"—fixed-size window, the classic pattern.
• "longest subarray such that [some constraint]"—variable-size window with expand/shrink.
• "shortest subarray with sum $\ge S$"—variable-size window (assuming non-negative elements).
• "number of subarrays satisfying [condition]"—often sliding window with counting.
• "fixed-size window" or "contiguous block of size $k$"—direct fixed-size slide.

Counter-examples—problems that look like sliding window but need a different approach:

• "Maximum subarray sum (any length, elements can be negative)." This is Kadane's algorithm, not sliding window. Negative elements break monotonicity—removing an element from the left can increase the sum instead of decreasing it.
• "Longest subarray where XOR equals target." XOR is its own inverse, so the window constraint is not monotonic—extending the window can both increase and decrease the XOR value. Use prefix XOR + hash map instead.
• "Count subarrays with sum exactly equal to $S$ (with negative numbers)." The "exactly $S$" part with negatives breaks both sliding window and the atMost(k) - atMost(k-1) inclusion-exclusion trick. Use prefix sums + hash map.

When sliding window does not work: The constraint must be monotonic. If expanding the window can both break and fix the constraint, a simple two-pointer slide is wrong. This happens with negative numbers in sum problems and XOR-based conditions.

---

C++ STL Reference

Sliding window problems lean on data structures that support efficient insertion and removal. These are the ones you will reach for most often.

Function / Class	Header	What it does	Time Complexity
deque<T>	<deque>	Double-ended queue. Push/pop both ends. Used for sliding window min/max.	$O(1)$ push/pop
multiset<T>	<set>	Sorted multiset. Insert/erase/find. Maintains window of sorted elements.	$O(\log n)$ per op
unordered_map<K,V>	<unordered_map>	Hash map for frequency counting in variable windows.	$O(1)$ amortized
map<K,V>	<map>	Ordered map. Useful when you need min/max key in the window.	$O(\log n)$ per op
accumulate(first, last, init)	<numeric>	Sum a range. Useful for initial window sum only (not per-step).	$O(n)$
priority_queue<T>	<queue>	Max-heap. Lazy deletion variant for sliding max.	$O(\log n)$ push/pop

---

Implementation (Contest-Ready)

Minimal Contest Template

Fixed-size window—maximum sum of subarray of length $k$:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long sum = 0, best = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (i >= k) sum -= a[i - k];
        // Invariant: sum = a[max(0,i-k+1)] + ... + a[i]
        if (i >= k - 1) best = max(best, sum);
        // Invariant: best = max sum over all complete windows seen so far
    }
    cout << best << "\n";
}

Variable-size window—longest subarray with sum $\le T$:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long T;
    cin >> n >> T;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long sum = 0;
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > T) sum -= a[l++];
        // Invariant: sum = a[l] + ... + a[r] <= T
        best = max(best, r - l + 1);
        // Invariant: best = max window length satisfying sum <= T so far
    }
    cout << best << "\n";
}

Explained Version

Fixed-size window—maximum sum of subarray of length $k$:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long sum = 0, best = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        // Expand: add the new right element to the window sum
        sum += a[i];

        // Shrink: once window exceeds size k, remove the leftmost element.
        // The element leaving is a[i - k] (the one that was at the left edge
        // of the previous window of size k).
        if (i >= k) sum -= a[i - k];

        // Invariant: sum = a[max(0,i-k+1)] + ... + a[i]
        // The window [i-k+1, i] has exactly k elements once i >= k-1.
        // Only then do we have a valid window to compare.
        if (i >= k - 1) best = max(best, sum);
        // Invariant: best = max sum over all complete windows [j-k+1..j] for j <= i
    }
    cout << best << "\n";
}

Variable-size window—longest subarray with sum $\le T$ (non-negative elements):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long T;
    cin >> n >> T;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long sum = 0;
    int best = 0;
    int l = 0; // left boundary of window [l, r]

    for (int r = 0; r < n; r++) {
        // Expand: include a[r] in the current window
        sum += a[r];

        // Shrink: if the window constraint is violated (sum > T),
        // advance l to restore it. This is a while, not an if --
        // we may need to remove multiple elements from the left.
        // Correctness relies on all a[i] >= 0 (monotonicity):
        // adding elements can only increase sum, removing can only decrease.
        while (sum > T) {
            // Invariant: sum = a[l] + ... + a[r], and sum > T so we must shrink
            sum -= a[l];
            l++;
        }

        // Invariant: sum = a[l] + ... + a[r] <= T
        // The window [l, r] now satisfies sum <= T.
        // Update the answer with the current window length.
        best = max(best, r - l + 1);
        // Invariant: best = max window length satisfying sum <= T for all r' <= r
    }
    cout << best << "\n";
}

Sliding window maximum with monotonic deque (fixed or variable size):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // dq stores *indices* in decreasing order of a[index].
    // Front of deque = index of current window maximum.
    deque<int> dq;

    for (int i = 0; i < n; i++) {
        // Remove elements from back that are <= a[i].
        // They can never be the maximum while a[i] is in the window.
        while (!dq.empty() && a[dq.back()] <= a[i])
            dq.pop_back();

        dq.push_back(i);

        // Remove front if it has fallen out of the window [i-k+1, i]
        if (dq.front() <= i - k)
            dq.pop_front();

        // Output maximum for each complete window
        if (i >= k - 1)
            cout << a[dq.front()] << " \n"[i == n - 1];
    }
}

---

Operations Reference

The base sliding window is $O(n)$; auxiliary structures add a log factor when you need more than sums.

Operation	Time	Space
Fixed-size window slide (sum/count)	$O(n)$	$O(1)$ extra
Variable-size window (two pointers)	$O(n)$	$O(1)$ extra
Sliding min/max with monotonic deque	$O(n)$	$O(k)$
Sliding window with frequency map	$O(n)$	$O(
Sliding window with multiset	$O(n\log k)$	$O(k)$
Sliding window with priority_queue (lazy deletion)	$O(n\log n)$ worst	$O(n)$
Sliding window median (two heaps)	$O(n\log k)$	$O(k)$

---

Problem Patterns & Tricks

Fixed-Size Aggregate (Sum, Count, XOR)

Maintain a running aggregate over a window of size $k$. When the window slides, subtract the leaving element and add the entering one. Works for any operation with an inverse—addition/subtraction, XOR/XOR, count increment/decrement.

for (int i = 0; i < n; i++) {
    sum += a[i];
    if (i >= k) sum -= a[i - k];
    if (i >= k - 1) ans = max(ans, sum);
}

Examples: CF 1176C, CF 1343C

Longest/Shortest Subarray with Constraint

Expand $r$ and shrink $l$ to maintain a constraint. Answer is $max(r-l+1)$ or $min(r-l+1)$.

Constraint must be monotonic: if $[l,r]$ violates the constraint, then $[l,r+1]$ also violates it (for "longest" problems), or $[l-1,r]$ also violates it.

Examples: CF 701C (distinct characters), CF 1611E

Sliding Window Maximum/Minimum (Monotonic Deque)

A deque maintains indices in monotonically decreasing (for max) or increasing (for min) order of values. The front is always the current extremum. Pop the front when it exits the window; pop the back when the new element dominates.

Each element is pushed and popped at most once, so total work is $O(n)$.

Examples: CF 940E, CF 1195E

Count of Subarrays with Exactly $k$ (Inclusion-Exclusion)

You cannot directly slide a window for "exactly $k$." Instead, compute:

$$\text{exactly}(k)=\text{atMost}(k)-\text{atMost}(k-1)$$

Each atMost call is a standard variable-size sliding window—this converts an "exactly" problem into two "at most" problems.

auto atMost = [&](int k) -> long long {
    long long cnt = 0;
    int l = 0;
    // ... maintain window with at most k of something
    for (int r = 0; r < n; r++) {
        // expand, shrink
        cnt += r - l + 1; // number of valid subarrays ending at r
    }
    return cnt;
};
long long ans = atMost(k) - atMost(k - 1);

Examples: CF 1234D, CF 844C

Sliding Window with Sorted Structure

When you need the min, max, median, or $k$-th element in the window, augment with multiset, two heaps, or a policy-based tree. Insert on expand, erase on shrink.

multiset<int> ms;
int l = 0;
for (int r = 0; r < n; r++) {
    ms.insert(a[r]);
    while (/* constraint violated */) {
        ms.erase(ms.find(a[l++]));
    }
    // *ms.begin() = window min, *ms.rbegin() = window max
}

Caution: Use ms.erase(ms.find(val)) not ms.erase(val)—the latter removes ALL copies.

Examples: CF 1538F, CF 1700D

String Anagram / Permutation Match

Slide a window of size $k$ over the text, maintaining a frequency difference array against the pattern. When all frequencies are zero, you have an anagram.

vector<int> freq(26, 0);
for (char c : pattern) freq[c - 'a']++;
int need = 26; // count of letters with freq != 0
for (int i = 0; i < 26; i++) if (freq[i] == 0) need--;
// ... slide and track when need == 0

Examples: CF 525C, CF 1800D

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                    SLIDING WINDOW CHEAT SHEET                     |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - Contiguous subarray/substring optimization                   |
|   - "Longest/shortest subarray with property X"                  |
|   - "Max/min over all windows of size k"                         |
|   - Constraint is MONOTONIC (no negatives in sum problems)       |
|                                                                  |
| FIXED-SIZE (k):                                                  |
|   sum += a[i]; if (i>=k) sum -= a[i-k];                         |
|   if (i>=k-1) ans = max(ans, sum);                               |
|                                                                  |
| VARIABLE-SIZE:                                                   |
|   for (r=0; r<n; r++) {                                          |
|       add(a[r]);                                                 |
|       while (bad()) remove(a[l++]);                              |
|       ans = max(ans, r-l+1);                                     |
|   }                                                              |
|                                                                  |
| SLIDING MAX/MIN: monotonic deque, O(n) total                    |
|   deque<int> dq; // stores indices, decreasing by value          |
|                                                                  |
| EXACTLY k = atMost(k) - atMost(k-1)                             |
|                                                                  |
| TIME:  O(n) basic, O(n log k) with multiset/heap                |
| SPACE: O(1) basic, O(k) with deque/multiset                     |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Common Mistakes

1. Off-by-one with window boundaries. Decide on half-open $[l,r)$ or closed $[l,r]$ and be consistent. Half-open is safer: window size is always $r-l$.

2. if vs while for shrinking. The inner shrink must be while, not if. One expansion can cause multiple violations requiring multiple shrinks.

3. Negative numbers break sum windows. If elements can be negative, removing one can increase the sum—monotonicity fails. Use prefix sums + binary search or a different technique.

4. multiset::erase(val) removes ALL copies. Always use ms.erase(ms.find(val)) to remove exactly one occurrence.

5. Empty window edge case. If all elements violate the constraint individually, $l$ can exceed $r$. Guard against this:

   while (sum > T && l <= r) sum -= a[l++];

6. Integer overflow. Window sums of ${10}^5$ elements each up to ${10}^9$ overflow int. Use long long.

7. Updating the answer too early. The answer update goes after the shrink loop, not inside it—inside the loop, the window is still invalid.

8. Deque: values vs indices. The deque stores indices but comparisons use a[dq.back()]. Mixing these up gives wrong answers silently.

9. Lazy deletion with priority_queue. When using a max-heap for sliding max, check that the top element is still inside the window before using it. Store (value, index) pairs.

Mental Traps

Trap 1: "Two-pointer and sliding window are the same thing." Two-pointer is a broad family: opposite-direction (pair sum on a sorted array), same-direction (merge two sorted lists), and window-based. Sliding window is one specific use of same-direction two pointers—maintaining an aggregate over a contiguous range. Conflating them leads you to try sliding window on pair-sum problems (wrong) or two-pointer merging on subarray problems (wrong).

  TWO POINTERS -- A FAMILY, NOT A SINGLE TECHNIQUE
  =================================================

  +------------------------------------+
  |          TWO POINTERS              |
  |                                    |
  |  +--------------+ +--------------+ |
  |  | Opposite     | |   Same       | |
  |  | direction    | | direction    | |
  |  | (pair sum,   | | (merge,      | |
  |  |  converge)   | |  window)     | |
  |  +--------------+ +------+-------+ |
  |                         |          |
  |               +---------+--------+ |
  |               |   SLIDING        | |
  |               |   WINDOW         | |
  |               | (aggregate       | |
  |               |  over range)     | |
  |               +------------------+ |
  +------------------------------------+

Trap 2: "The window always resizes in O(1)." For sum, count, or XOR—yes, add/remove is $O(1)$. But sliding min/max with a deque is amortized $O(1)$; sorted order via multiset is $O(\log k)$ per add/remove; median (two heaps) is $O(\log k)$. The per-operation cost changes total complexity from $O(n)$ to $O(n\log k)$. Always account for your window's data-structure cost.

---

Self-Test

Answer these without looking at the file. If you cannot, re-read the relevant section.

• [ ] Write the variable-size sliding window template (expand r, shrink l while invalid) from memory, with the aggregate update in the correct place.
• [ ] Explain the amortized $O(n)$ argument: why is total pointer movement bounded by $2n$?
• [ ] Implement sliding window maximum using a monotonic deque—state the deque invariant.
• [ ] State the monotonicity condition a problem must satisfy for sliding window to work, and give one example that satisfies it and one that does not.
• [ ] Distinguish fixed-size window from variable-size window—write the loop skeleton for each.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Maximum Sum of Almost Unique Subarray	CF 1912B	1200	Fixed window, count distinct with map
2	Distinct Characters Queries	CF 1234D	1300	Fixed window frequency counting
3	They Are Everywhere	CF 701C	1500	Variable window, all types present
4	Longest Subarray	CF 1611E	1500	Variable window with max constraint
5	Kuroni and Impossible Calculation	CF 1305C	1600	Window + pigeonhole
6	Playlist	CF 1702E	1600	Sliding window + set
7	Sliding Window Maximum	CSES	1700	Monotonic deque, classic
8	Segment with Small Spread	CF 1538F	1800	Variable window + multiset for min/max
9	Ehab and Prefix MEXs	CF 1364D	2100	Advanced window technique with MEX

---

Further Reading

• cp-algorithms: Two Pointers—foundational technique behind sliding window
• CF Blog: Sliding Window Technique—community overview with examples
• USACO Guide: Sliding Window—structured progression with problems

See Also

• Two Pointers—prerequisite technique; sliding window is a specialized two-pointer pattern
• Prefix Sums—alternative for range-sum queries, especially when elements can be negative
• Sorting and Searching—sorting often preprocesses input before a window pass
• Monotonic Queue—deque-based sliding min/max in depth
• Data Structures overview—deque, multiset, and heap patterns used inside windows
• Data Structure Selection Guide—choosing the right auxiliary structure for your window
• Practice Ladder 1100–1400—introductory problems including sliding window drills

---

Code Reading Exercise

What does this code compute? Work it out before checking the answer.

int solve(vector<int>& a) {
    int n = a.size();
    long long ans = 0;
    unordered_map<int, int> cnt;
    for (int i = 0, j = 0; i < n; i++) {
        cnt[a[i]]++;
        while (cnt[a[i]] > 1) {
            cnt[a[j]]--;
            if (cnt[a[j]] == 0) cnt.erase(a[j]);
            j++;
        }
        ans += i - j + 1;
    }
    return ans;
}

Answer

This counts the total number of subarrays where all elements are distinct. The window [j..i] maintains the invariant that every element appears exactly once. For each right endpoint i, there are exactly (i - j + 1) valid subarrays ending at i—namely [j..i], [j+1..i], ..., [i..i]. Summing these counts gives the total.

---

What does this code compute?

int solve(vector<int>& a) {
    int n = a.size();
    int total = set<int>(a.begin(), a.end()).size();
    unordered_map<int, int> cnt;
    int have = 0, ans = n + 1;
    for (int i = 0, j = 0; i < n; i++) {
        if (++cnt[a[i]] == 1) have++;
        while (have == total) {
            ans = min(ans, i - j + 1);
            if (--cnt[a[j]] == 0) have--;
            j++;
        }
    }
    return ans;
}

Answer

This finds the length of the shortest subarray that contains every distinct value present in the full array. It first counts how many distinct values exist (total), then uses a variable-size sliding window: expand right until all values are covered, then shrink left to minimize the window, recording the best length found.

---

What to Solve Next

1. Master the basics first. Solve problems 1–4 from the Practice Problems table until fixed and variable windows are automatic.
2. Add a data structure. Try problem 7 (monotonic deque) and problem 8 (multiset window). See Monotonic Queue for the deque deep dive.
3. Learn when to switch tools. When negative numbers appear and sliding window breaks, Prefix Sums often takes over.
4. Climb the ladder. Work through the sliding window problems in Practice Ladder 1100–1400, then advance to Ladder 1400–1700.