Sliding Window

The sliding window technique is a powerful approach for solving problems involving subarrays. It works by maintaining a subarray (window) of elements and moving (sliding) this window across the data to compute results efficiently.

Introduction

When I first learned the sliding-window trick for sum, it felt like magic: out went an O(n·K) double loop, in came an O(n) solution. Then I tried to do the same for minimum and promptly got stuck. You can’t “subtract” a minimum!

In this tutorial you’ll learn:
1. How invertible operators (sum, XOR) let you slide in O(n)
2. Why non-invertible operators (min, max, GCD…) break the simple trick
3. A general O(n) approach using two stacks and aggregation

1. Invertible Operators: Sum & XOR

If you can undo your operation in O(1), the sliding window is trivial.

1.1 Fixed-Size Window Sum

vector<int> slideSum(const vector<int>& a, int K) {
    int n = a.size(), sum = 0;
    vector<int> ans;
    // initial window
    for (int i = 0; i < K; ++i)
        sum += a[i];
    ans.push_back(sum);
    // slide: add new, subtract old
    for (int i = K; i < n; ++i) {
        sum += a[i];          // enter
        sum -= a[i - K];      // leave
        ans.push_back(sum);
    }
    return ans;
}

1.2 Fixed-Size Window XOR

vector<int> slideXor(const vector<int>& a, int K) {
    int n = a.size(), xr = 0;
    vector<int> ans;
    // initial window
    for (int i = 0; i < K; ++i)
        xr ^= a[i];
    ans.push_back(xr);
    // slide: include new, exclude old
    for (int i = K; i < n; ++i) {
        xr ^= a[i];          // enter
        xr ^= a[i - K];      // leave
        ans.push_back(xr);
    }
    return ans;
}

Why it works: x ^ x = 0, re-XOR the outgoing element undoes it in O(1).

2. The Challenge: Non-Invertible Operators

For Min / Max, Bitwise OR / AND, GCD / LCM etc., there is no efficient “remove” step.

For Min / Max; We can use multisets, but that will make the solution O(N log(N))

For Bitwise OR / AND, GCD / LCM: We can't use multisets to get our answer, we will need some other data structures like sparse table / segment trees.

Let's look at an easier and efficient idea to handle all of these operations:

Insight: A sliding window acts as a queue
- push an element at the back when a new element enters
- pop an element from the front when the old one leaves

What if our queue could also answer “what’s the min?” in O(1)?

3. Implement a Queue with Two Stacks

A simple, classic trick to get amortized O(1) push/pop operations is using two stacks:

#include <stack>
using namespace std;

struct MyQueue {
    stack<int> in, out;

    // Push a new element into the queue.
    void push(int x) {
        in.push(x);
    }

    // Pop the oldest element from the queue.
    void pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        out.pop();
    }

    // Return the oldest element.
    int front() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        return out.top();
    }
};

• The in stack collects new items.
• When needing to pop or peek the oldest, items are transferred from in to out.

4. Augmented Stack for Aggregates (Min Stack Problem)

A simplified approach to track the minimum in a stack is to store each value along with the current minimum up to that point:

struct AggStack {
    // Each element is stored as (value, current_min)
    stack<pair<int, int>> st;
    
    // Push a new number; compute the new min.
    void push(int x) {
        int cur = st.empty() ? x : min(st.top().second, x);
        st.push({x, cur});
    }
    
    // Pop the top element.
    void pop() {
        st.pop();
    }
    
    // Return the current minimum.
    int agg() const {
        return st.top().second;
    }
};

Each push/pop here works in O(1).

5. Aggregated Queue & Sliding-Window Minimum

We now combine two augmented stacks to create an aggregated queue that can give the current minimum in O(1):

struct AggQueue {
    AggStack in, out;
    
    // Push a new number into the queue.
    void push(int x) {
        in.push(x);
    }
    
    // Pop the oldest number.
    void pop() {
        if (out.st.empty()) {
            while (!in.st.empty()) {
                int v = in.st.top().first;
                in.pop();
                out.push(v);
            }
        }
        out.pop();
    }
    
    // Query the current minimum.
    int query() const {
        if (in.st.empty()) return out.agg();
        if (out.st.empty()) return in.agg();
        return min(in.agg(), out.agg());
    }
};

vector<int> slideMin(const vector<int>& a, int K) {
    int n = a.size();
    vector<int> ans;
    AggQueue mq;  // Our aggregated queue maintains the minimum
    
    // Build the initial window of size K.
    for (int i = 0; i < K; i++) {
        mq.push(a[i]);
    }
    ans.push_back(mq.query());
    
    // Slide the window: add a new element and remove the oldest.
    for (int i = K; i < n; i++) {
        mq.push(a[i]);   // add new element
        mq.pop();        // remove element that's left the window
        ans.push_back(mq.query());
    }
    
    return ans;
}

Note: You can modify the AggStack and AggQueue to work with other aggregates (e.g., maximum, GCD) by replacing min with the appropriate function.

Practice Problems

• Sliding Window Sum
• Sliding Window XOR
• Sliding Window Distinct Values
• Sliding Window Minimum
• Sliding Window OR
• Sliding Window Median (also requires ordered set / two priority queues or multisets)
• Sliding Window Cost (same idea as median)