Back to solutions

Sliding Window Maximum

HardSliding Window

Return the maximum of every contiguous window of size k as it slides across the array.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 1 <= k <= n

Monotonic deque of indices

Time O(n)Space O(k)

Keep a deque of indices whose values decrease front to back. Pop smaller values from the back when adding a new one and drop indices that fall out of the window; the front is always the window maximum.

#include <bits/stdc++.h>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> res;
    for (int i = 0; i < (int)nums.size(); i++) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}