⚙️AlgorithmIntermediate

Sliding Window

Key Points

  • •
    Sliding window is a technique that moves a contiguous segment (window) across an array or string while maintaining some running information like sum, count, or max.
  • •
    Fixed-size windows keep the window length constant and update state by adding the new right element and removing the old left element in O(1) time per move.
  • •
    Variable-size windows expand the right end until a condition is violated, then shrink the left end until the condition is restored, ensuring O(n) total moves.
  • •
    Using a monotonic deque lets you get the minimum or maximum of the current window in O(1) amortized time per step, giving O(n) overall.
  • •
    The key invariant is that the maintained window always satisfies a property (e.g., at most K distinct, no repeats, ) after each adjustment.
  • •
    Sliding window often reduces O() brute-force subarray checks to O(n) or O(n log n) solutions.
  • •
    This technique works best when the property is monotone under shrinking or expanding (e.g., with non-negative numbers for sum constraints).
  • •
    Common pitfalls include using it with negative numbers for sum constraints, forgetting to evict out-of-window elements, and off-by-one index mistakes.

Prerequisites

  • →Arrays and indexing — Windows are contiguous segments defined by indices; careful indexing avoids off-by-one errors.
  • →Big-O notation — Understanding why pointer movements lead to O(n) time requires asymptotic reasoning.
  • →Hash maps / frequency arrays — Variable windows often track counts of elements to enforce constraints like distinctness.
  • →Deques and queues — Monotonic deque implementations rely on efficient front/back operations.
  • →Algorithmic invariants — Maintaining and restoring a window property is central to correctness.
  • →Amortized analysis basics — Explains how nested while-loops still lead to O(n) total operations.

Detailed Explanation

Tap terms for definitions

01Overview

Sliding window is an algorithmic pattern for processing contiguous segments of arrays or strings efficiently. Instead of recomputing results from scratch for every subarray, we maintain a "window" that moves across the data, updating a compact summary (like sum, max, or frequencies) as we slide. There are two common variants. In a fixed-size window, the window length is constant (size k), and at each step we add the new rightmost element while removing the leftmost. In a variable-size window, the window length changes: we expand the right boundary to accumulate more elements until a constraint is broken, then shrink the left boundary until the constraint is satisfied again. A powerful extension uses a monotonic deque to track the best (max/min) element in the current window in O(1) amortized time. Sliding window is especially valuable when the target property is local, monotone under expansion/shrinking, or can be updated incrementally. This pattern yields linear-time solutions for a wide range of problems that would otherwise require quadratic time if we naively re-evaluated each subarray.

02Intuition & Analogies

Imagine looking out of a train window at a long fence with colored boards. You can’t see the entire fence at once, only a portion—the window view. As the train moves, the scene shifts by one board: a new board appears on the right, and one disappears on the left. If you were counting the number of red boards in view, you would not recount everything from scratch each time. You’d simply add 1 if the new board is red and subtract 1 if the board that left was red. That is the fixed-size sliding window. Now imagine you’re searching for the longest stretch where the number of red boards never exceeds K. You’d slide the right edge forward, growing the view until the count goes over K, then move the left edge forward to remove boards until you’re back under the limit. This ebb and flow is the variable-size sliding window, where you maintain a rule (an invariant) by balancing growth and shrinkage. Sometimes you care about the tallest board in view. You could keep a short list of candidate tall boards decreasing by height; when a new, taller board arrives, shorter ones to its left are irrelevant and get dropped. This is the monotonic deque idea—always keep the best candidates in order so the top is instantly available.

03Formal Definition

Given a sequence A[0..n-1], a sliding window is an index interval [L, R] where 0 ≤ representing a contiguous subarray A[L..R]. The algorithm maintains a compact state S(L, R) that summarizes properties of A[L..R] (e.g., sum, maximum, counts) and updates S as L and/or R move. In the fixed-size variant, R increases by 1 each step and − k + 1, maintaining constant window length k. In the variable-size variant, R increases monotonically, while L increases as needed to restore an invariant P(A[L..R]) (e.g., at most K distinct elements, no duplicates, for positive arrays). The efficiency relies on incremental updates S(L, R+1) and/or S(L+1, R) computable in O(1) or amortized O(1), ensuring at most O(n) total pointer movements. With a monotonic deque D storing indices, we maintain either non-increasing A[D[i]] for maximum (or non-decreasing for minimum), evicting indices outside [L, R] and those dominated by the incoming element. Each index is inserted and removed at most once, yielding amortized O(1) per step. Hash maps or frequency arrays can maintain counts for properties like distinctness within O(1) expected time.

04When to Use

Use a fixed-size window when the subarray length is given (e.g., moving average, sum of every k-length subarray, max/min over each window). Use a variable-size window when a constraint is monotone with respect to expanding or shrinking: examples include longest substring without repeating characters, longest subarray with at most K distinct values, minimum length subarray with sum at least S when numbers are non-negative, and counting subarrays that satisfy a threshold under non-negative inputs. Use a monotonic deque for window extrema (max/min) in O(n) time, far outperforming naive O(nk) scans. Prefer frequency arrays (size 26/52/128/256) for character problems and small integer alphabets, and unordered_map for general keys. Avoid sliding window for constraints that are not monotone (e.g., sums with negative numbers can increase or decrease unpredictably when you move L or R), or when the required property depends on non-local information that cannot be updated incrementally. If ordered statistics (k-th smallest) or medians are needed in a sliding window, consider specialized structures (heaps with lazy deletion, order-statistics trees) which may yield O(n log k) rather than O(n).

⚠️Common Mistakes

  1. Applying sliding window to sums with negative numbers: shrinking may not reduce the sum, breaking the monotonicity argument. Either restrict to non-negative numbers or switch to other techniques (prefix sums + binary search, Kadane’s algorithm, or two-pointer with caution under sorted/prefix constraints). 2) Forgetting to evict elements that leave the window: when R advances, ensure the contribution of L is subtracted or its count is decremented; with deques, remove indices that fall left of L. 3) Off-by-one errors: mixing 0-based and 1-based lengths, updating L and R in the wrong order, or computing window length as R-L (instead of R-L+1). 4) Assuming O(1) hash map operations without considering worst-case: unordered_map is average O(1) but can degrade; for predictable small alphabets, prefer fixed-size arrays. 5) Breaking the invariant when shrinking: in variable windows, shrink inside a while-loop until the invariant is fully restored; a single step may be insufficient. 6) Using sorted containers unnecessarily: maintaining max/min with a multiset is O(log k) per step; a monotonic deque achieves amortized O(1). 7) Not guarding k edge cases: k ≤ 0 or k > n should be handled explicitly. 8) Ignoring integer overflow when maintaining sums: use 64-bit types (long long) for large values.

Key Formulas

Fixed Window Sum Update

Explanation: The sum of the next k-length window equals the current sum minus the element that leaves and plus the new element that enters. This enables O(1) updates per slide.

Two-Pointer Amortized Bound

Explanation: Each pointer only increases from 0 to n−1, so total increments are at most 2n. Thus, even with nested while-loops, the overall time is linear.

Prefix Sum Range Formula

Explanation: Prefix sums let you compute the sum of any subarray in O(1) time. While sliding windows avoid recomputation incrementally, this identity is useful for reasoning and checks.

Counting Subarrays in Valid Window

Explanation: When a variable window [L, R] is valid under a monotone property, all subarrays ending at R and starting in [L, R] are valid. The number of such subarrays is the window length.

Deque Amortized Operations

Explanation: Each index is pushed at most once and popped at most once from a monotonic deque. Therefore, total deque operations are linear, implying O(n) overall time.

Max/Min Over Window Complexity

Explanation: Scanning k elements to find each window's maximum costs O(nk). A monotonic deque reduces this to linear time by reusing previous work.

Asymptotic Improvement

Explanation: If each window update can be done in constant time and pointers move monotonically, total runtime becomes linear, improving over sorting or recomputation approaches.

Complexity Analysis

Sliding window achieves linear time primarily because both endpoints L and R move monotonically from left to right. In the fixed-size variant, R advances n times, and each step performs O(1) updates (add new right element, remove old left element), so the total time is O(n). In the variable-size variant, even with a nested while-loop to shrink the window, each increment of L and R happens at most n times in total. Hence, the amortized per-element cost is O(1), yielding O(n) total time. Using auxiliary structures affects constants and sometimes asymptotics: a frequency array or unordere maintains counts in expected O(1) per change; an ordered map would cost O(log per change, where σ is alphabet size, leading to O(n log For window extrema, a monotonic deque provides amortized O(1) updates because each element is inserted once and removed at most once; thus overall complexity remains O(n). Space complexity is typically O(1) or O(k) for fixed-size windows to store state, O( for frequency maps (σ is the domain size), and O(k) for the deque when tracking max/min. When sums can overflow 32-bit integers, use 64-bit types to avoid errors without changing time complexity. Beware that sliding window’s O(n) guarantee for sum constraints assumes non-negative values; with negative numbers, invariants break, and alternative methods may be required.

Code Examples

Fixed-size window: Moving average of last k elements
1#include <bits/stdc++.h>
2using namespace std;
3
4// Compute moving average over every contiguous window of size k.
5// Returns a vector of double with n - k + 1 entries.
6vector<double> movingAverage(const vector<int>& a, int k) {
7    int n = (int)a.size();
8    if (k <= 0 || k > n) return {}; // handle edge cases
9    vector<double> res;
10    res.reserve(n - k + 1);
11    long long sum = 0; // use 64-bit to avoid overflow
12
13    // Build the first window [0, k-1]
14    for (int i = 0; i < k; ++i) sum += a[i];
15    res.push_back((double)sum / k);
16
17    // Slide the window: remove a[i - k], add a[i]
18    for (int i = k; i < n; ++i) {
19        sum += a[i];
20        sum -= a[i - k];
21        res.push_back((double)sum / k);
22    }
23    return res;
24}
25
26int main() {
27    ios::sync_with_stdio(false);
28    cin.tie(nullptr);
29
30    vector<int> a = {1, 3, 2, 6, -1, 4, 1, 8, 2};
31    int k = 5;
32    auto avg = movingAverage(a, k);
33
34    cout << fixed << setprecision(2);
35    for (double x : avg) cout << x << " ";
36    cout << "\n";
37    return 0;
38}
39

We maintain the sum of the current k-length window. To slide by one, we subtract the element that leaves and add the new element that enters. The average is sum/k for each position.

Time: O(n)Space: O(1) extra (excluding output)
Variable-size window: Longest substring without repeating characters
1#include <bits/stdc++.h>
2using namespace std;
3
4// Returns the length of the longest substring with all unique characters.
5int lengthOfLongestSubstring(const string& s) {
6    vector<int> cnt(256, 0); // ASCII frequency
7    int n = (int)s.size();
8    int best = 0;
9    int L = 0;
10    for (int R = 0; R < n; ++R) {
11        unsigned char c = (unsigned char)s[R];
12        cnt[c]++;
13        // Shrink until no character repeats
14        while (cnt[c] > 1) {
15            unsigned char left = (unsigned char)s[L++];
16            cnt[left]--;
17        }
18        best = max(best, R - L + 1);
19    }
20    return best;
21}
22
23int main() {
24    ios::sync_with_stdio(false);
25    cin.tie(nullptr);
26
27    string s = "abcabcbb"; // answer: 3 ("abc")
28    cout << lengthOfLongestSubstring(s) << "\n";
29    return 0;
30}
31

We expand the right boundary and track character counts. If we introduce a duplicate, we shrink from the left until the window has no repeats again. The invariant is that the window contains only unique characters.

Time: O(n)Space: O(1) for fixed alphabet (256)
Monotonic deque: Sliding window maximum
1#include <bits/stdc++.h>
2using namespace std;
3
4// Compute the maximum for each window of size k using a decreasing deque.
5vector<int> slidingWindowMax(const vector<int>& a, int k) {
6    int n = (int)a.size();
7    if (k <= 0 || k > n) return {};
8    deque<int> dq; // stores indices; values are decreasing: a[dq[0]] >= a[dq[1]] >= ...
9    vector<int> ans;
10    ans.reserve(n - k + 1);
11
12    for (int i = 0; i < n; ++i) {
13        // Remove indices outside the window's left bound (i - k + 1)
14        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
15        // Maintain decreasing order: remove smaller elements from the back
16        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
17        dq.push_back(i);
18        // The front is the maximum of the current window
19        if (i >= k - 1) ans.push_back(a[dq.front()]);
20    }
21    return ans;
22}
23
24int main() {
25    ios::sync_with_stdio(false);
26    cin.tie(nullptr);
27
28    vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
29    int k = 3; // expected: 3,3,5,5,6,7
30    auto res = slidingWindowMax(a, k);
31    for (int x : res) cout << x << ' ';
32    cout << '\n';
33    return 0;
34}
35

The deque stores indices of elements in decreasing order of their values; the front is always the maximum within the current window. Before pushing a new index, we discard smaller values behind it, since they can never become maximum later.

Time: O(n)Space: O(k)
Variable-size window: Minimum length subarray with sum at least S (non-negative numbers)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Find the minimal length of a contiguous subarray of which the sum >= target.
5// Assumes nums contains non-negative integers (monotonicity is required).
6int minSubArrayLen(int target, const vector<int>& nums) {
7    int n = (int)nums.size();
8    long long sum = 0;
9    int L = 0;
10    int best = INT_MAX;
11    for (int R = 0; R < n; ++R) {
12        sum += nums[R];
13        // Shrink while the window still satisfies sum >= target
14        while (sum >= target) {
15            best = min(best, R - L + 1);
16            sum -= nums[L++];
17        }
18    }
19    return best == INT_MAX ? 0 : best; // return 0 if no such subarray exists
20}
21
22int main() {
23    ios::sync_with_stdio(false);
24    cin.tie(nullptr);
25
26    vector<int> nums = {2, 3, 1, 2, 4, 3};
27    int target = 7; // expected: 2 (subarray {4,3})
28    cout << minSubArrayLen(target, nums) << "\n";
29    return 0;
30}
31

We expand the right boundary to increase the sum and shrink from the left to minimize the window while keeping the sum ≥ target. This relies on non-negative numbers so that expanding never decreases the sum and shrinking never increases it.

Time: O(n)Space: O(1)