Skip to content

Sliding Window Minimum / Maximum

Given an array and a fixed window size \(k\), report the minimum (or maximum) in every contiguous window of length \(k\) in amortized \(O(n)\) using a monotonic deque—indices with values increasing (for min) from front to back.

Minimum in each window

#include <vector>
#include <deque>
using namespace std;

// Returns size n - k + 1 values: min of a[i..i+k-1] for i = 0..n-k
vector<int> slidingWindowMin(const vector<int>& a, int k) {
    int n = (int)a.size();
    vector<int> res;
    deque<int> dq; // indices; a[dq.front] .. smallest in current window
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        while (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

For maximum, use <= in the back pop condition (while ... a[dq.back()] <= a[i]).

Complexity

Each index is pushed and popped from the deque at most once → \(O(n)\) total for fixed \(k\).