Sliding Window

Sliding Window

From CPH:

A sliding window is a constant-size subarray that moves from left to right through the array.

For each position of the window, we want to compute some information.

Implementation

The most straightforward way to do this is to store an ordered set of integers representing the integers inside the window. If the window currently spans the range $i \dots j$, we observe that moving the range forward to $i+1 \dots j+1$ only removes $a_i$ and adds $a_{j+1}$ to the window. We can support these two operations and query for the minimum / maximum in the set in $O(\log N)$.

Time Complexity: $\mathcal{O}(N\log N)$

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    multiset<int> s;
    vector<int> ret;
    for(int i = 0; i < k; i++){
        s.insert(nums[i]);
    }
    for(int i = k; i < nums.size(); i++){
        ret.push_back(*s.rbegin());
        s.erase(s.find(nums[i-k]));
        s.insert(nums[i]);

Problems

With Two Pointers

In general, it is not required for the subarray to have constant size as long as both the left and right endpoints of the subarray only move to the right.

Solution

int n;
set<int> s;
int a[200000], ans;

int main() {
    int r = -1;
    cin >> n; F0R(i,n) cin >> a[i];
    F0R(i,n) {
        while (r < n-1 && !s.count(a[r+1])) s.insert(a[++r]);
        ans = max(ans,r-i+1);

Problems

Sliding Window Minimum in $O(N)$

Resources

Method 1 - Deque

Method 2 from cp-algo.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> d;
    vector<int> ret;
    for(int i = 0; i < k; i++){
        while(!d.empty() && nums[i] > nums[d.back()]){
            d.pop_back();
        }
        d.push_back(i);
    }
    for(int i = k; i < nums.size(); i++){

Method 2 - Two Stacks

Method 3 from cp-algo. Not as common but nice to know!

Problems