2Brute2Best
🔥0

Sliding Window Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Keep a current range [left … right] and slide it across the array, updating what you know instead of recomputing it.

6 sub-patterns · 34 questions

Remember this · Sliding Window
Trigger
Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".
Think
Can I keep a valid range and move it, instead of checking every subarray from scratch?
Key question
When is my current window valid?
A

What is this pattern?

Many problems ask about a contiguous piece of an array or string: the longest, the shortest, the biggest sum, how many of them.

The slow way checks every possible piece, rebuilding each from scratch. Sliding Window keeps one current piece [left … right] and moves its edges as you scan. When right moves, one element comes in. When left moves, one element goes out. You only update what changed.

Everything between left and right is your current window.

Think of reading a long sentence through a cardboard frame. You don't cut out a new frame for every position — you slide the same frame along, and only the letters at its edges change.

B

See it move

Longest subarray with sum ≤ 7. R always moves forward. L moves only when the window breaks the rule.

Expand right, shrink leftarr = [2, 1, 5, 1, 3, 2], limit = 7step 1/12
arr
0
1
2
3
4
5
2
1
5
1
3
2
▲L R
State
sum
2
limit
7
best
0
sum 2 ≤ 7 → valid

R moves to 0: 2 enters the window.

C

How do I recognise it?

  • The answer is a contiguous subarray or substring (not a subsequence, not any subset).

  • The question asks for the longest / shortest / maximum / minimum such piece, or how many pieces.

  • There is a fixed size ("of size k", "every k consecutive").

  • There is a limit: "at most k distinct", "sum ≤ target", "at most k replacements", "no repeating characters".

  • The rule can be checked from a small summary you can update when one element enters or leaves (a sum, a count map, a set).

Looks like Sliding Window, but isn't

Subarray sum equals K, and the array has negative numbers
→ Prefix Sum + hash map

With negatives, adding an element can make the sum smaller. Moving left might make things worse or better — there is no safe rule for when to shrink.

Longest increasing subsequence / any subsequence
→ Dynamic Programming

A subsequence can skip elements. A window cannot — it is always a solid block.

Pair of elements with a target sum in a sorted array
→ Two Pointers (opposite ends)

You care about two specific elements, not about everything between them.

Count subarrays with exactly K of something
→ Sliding Window, but as atMost(K) − atMost(K − 1)

"Exactly K" is not monotonic — shrinking can move you from too many to too few. "At most" is monotonic, so count two of those.

D

How would I discover it from scratch?

Don't memorise “use sliding window”. Ask these questions in order — the pattern falls out.

Try every start i and every end j, and check the piece arr[i..j]. That is O(N²) pieces, and checking each may cost more.

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Fixed Window

7 questions

The window size is given and never changes. You never decide when to shrink — every step you add one element on the right and remove one on the left.

02

Variable Window

7 questions

The window grows and shrinks. You grow it on the right every step, and shrink it from the left only when it breaks a rule.

03

Variable Window + Frequency Map

7 questions

A variable window whose rule depends on counts inside it — how many distinct values, how often the most common letter appears, whether required letters are all present.

04

At Most / At Least K (counting)

5 questions

Count how many subarrays satisfy a rule instead of finding the best one. For an at most rule, every start from left to right is valid for the current right end. For an at least rule, it flips: once the window is good, every start before left (or every extension to the right) is good too.

05

Exactly K

4 questions

Count subarrays with exactly K of something. Direct windows fail, so compute atMost(K) − atMost(K − 1).

06

Window + Monotonic Deque

4 questions

You need the max or min of the current window at every step. A deque keeps candidates in sorted order and throws away elements that can never be the answer again.

F

Don't mix these up

Fixed window vs Variable window

Is the size given (fixed) or is the size the answer (variable)? If you see "of size k", it is fixed.

Fruit Into Baskets vs Longest Repeating Character Replacement

Both are longest windows with a count map. Fruit: valid when distinct types ≤ 2. Replacement: valid when window size − max frequency ≤ k. Same pattern, different validity rule.

At most K vs Exactly K

At most is monotonic (shrinking always helps), so one window works. Exactly is not — use atMost(K) − atMost(K−1).

At most K (count) vs At least K (count)

At most: the window keeps the valid part, so add right − left + 1. At least: shrink while it is still good, then add left — every start before left makes a good subarray.

Sliding window vs Prefix sum + hash map

Negative numbers in a sum problem break the window. If adding an element can make the window more valid, you cannot shrink greedily — use prefix sums.

Shortest sum ≥ k (positives) vs Shortest sum ≥ k (with negatives)

All positive → plain variable window (Minimum Size Subarray Sum). Negatives allowed → shrinking is no longer safe; use prefix sums + a monotonic deque (Shortest Subarray with Sum at Least K).

G

Code templates (C++)

Fixed window

Size never changes: one add, one remove per step. No while loop.

fixed-template.cpp
// Fixed window of size k: add the element entering, remove the element leaving.
long long fixedWindow(vector<int>& a, int k) {
    long long window = 0, best = LLONG_MIN;
    for (int right = 0; right < (int)a.size(); right++) {
        window += a[right];                 // 1. element enters on the right
        if (right >= k) window -= a[right - k]; // 2. element leaves on the left
        if (right >= k - 1) best = max(best, window); // 3. window is full: use it
    }
    return best;
}

Variable window (longest valid)

add, remove and valid are placeholders — they change per problem. The loop shape stays the same. For the shortest valid window, update the answer inside the while loop instead.

variable-template.cpp
// Variable window: grow on the right, shrink on the left while invalid.
int longestValidWindow(vector<int>& a) {
    int left = 0, best = 0;
    // state describing the current window (sum, counts, ...)
    for (int right = 0; right < (int)a.size(); right++) {
        add(a[right]);                    // 1. expand: include a[right]
        while (!valid()) {                // 2. shrink until valid again
            remove(a[left]);
            left++;
        }
        best = max(best, right - left + 1); // 3. window [left..right] is valid
    }
    return best;
}

Counting: at most K / exactly K

Each right end contributes right − left + 1 subarrays.

atmost-template.cpp
// Count subarrays satisfying an "at most" rule.
// For a fixed right end, every start in [left..right] is valid.
long long countAtMost(vector<int>& a, int k) {
    if (k < 0) return 0;                  // "at most -1" is impossible (use k <= 0 for distinct counts)
    long long count = 0;
    int left = 0;
    for (int right = 0; right < (int)a.size(); right++) {
        add(a[right]);
        while (!valid(k)) { remove(a[left]); left++; }
        count += right - left + 1;        // subarrays ending at right
    }
    return count;
}

// "Exactly K" is not monotonic, so use two "at most" counts:
long long countExactly(vector<int>& a, int k) {
    return countAtMost(a, k) - countAtMost(a, k - 1);
}

Window + monotonic deque

Keeps only elements that could still be the maximum. Each index is pushed and popped once → O(N).

deque-template.cpp
// Maximum of every window of size k using a monotonic deque.
// dq holds indices; their values are in decreasing order front -> back.
vector<int> windowMax(vector<int>& a, int k) {
    deque<int> dq;
    vector<int> res;
    for (int right = 0; right < (int)a.size(); right++) {
        while (!dq.empty() && a[dq.back()] <= a[right]) dq.pop_back(); // can never be max again
        dq.push_back(right);
        if (dq.front() <= right - k) dq.pop_front();                 // fell out of the window
        if (right >= k - 1) res.push_back(a[dq.front()]);            // front = current max
    }
    return res;
}
Next
Start with Fixed Window