# 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↵
↵
```cpp↵
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↵
↵
```cpp↵
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:↵
↵
```cpp↵
#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:↵
↵
```cpp↵
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):↵
↵
```cpp↵
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());↵
}↵
};↵
```↵
↵
↵
```cpp↵
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](https://cses.fi/problemset/task/3220) ↵
- [Sliding Window XOR](https://cses.fi/problemset/task/3426) ↵
- [Sliding Window Distinct Values] (https://cses.fi/problemset/task/3222)↵
- [Sliding Window Minimum](https://cses.fi/problemset/task/3221) ↵
- [Sliding Window OR](https://cses.fi/problemset/task/3405)↵
- [Sliding Window Median] (https://cses.fi/problemset/task/1076) (also requires ordered set / two priority queues or multisets)↵
- [Sliding Window Cost] (https://cses.fi/problemset/task/1077) (same idea as median)
↵
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↵
↵
```cpp↵
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↵
↵
```cpp↵
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:↵
↵
```cpp↵
#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:↵
↵
```cpp↵
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):↵
↵
```cpp↵
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());↵
}↵
};↵
```↵
↵
↵
```cpp↵
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](https://cses.fi/problemset/task/3220) ↵
- [Sliding Window XOR](https://cses.fi/problemset/task/3426) ↵
- [Sliding Window Distinct Values] (https://cses.fi/problemset/task/3222)↵
- [Sliding Window Minimum](https://cses.fi/problemset/task/3221) ↵
- [Sliding Window OR](https://cses.fi/problemset/task/3405)↵
- [Sliding Window Median] (https://cses.fi/problemset/task/1076) (also requires ordered set / two priority queues or multisets)↵
- [Sliding Window Cost] (https://cses.fi/problemset/task/1077) (same idea as median)
