Sliding Window Maximum — Monotonic Deque

What does it solve?

For every window of fixed width k sliding across the array, report the maximum. The brute force rescans each window in O(N·k); a deque brings it to O(N).

Key insight: maintain a monotonic decreasing deque of indices. Before pushing a new index, pop every smaller value off the back (they can never be a future max while this bigger one is around). Pop the front if it has slid out of the window. The front is always the current maximum, read in O(1). Each index is pushed and popped once → O(N).

The core idea

// dq holds indices, values decreasing
for i in 0..n-1:
  if dq.front <= i-k: pop front
  while a[dq.back] <= a[i]: pop back
  dq.push(i)
  if i >= k-1: output a[dq.front]

Complexity

Time complexity

O(N)

Every index enters and leaves the deque exactly once, so the total push/pop work is linear, no matter the window size k.

Space complexity

O(k)

The deque never holds more than k indices at a time. The output array is O(N−k+1) but that's the required result.

Examples & edge cases

Live animation — monotonic deque, max always at the front

incoming a[i] in window popped / evicted deque front = max

nums · k = —

Monotonic deque (indices, values decreasing front → back)

empty

Window maxima (output)

none yet

Current step detail

i = — window = — deque = — max = —

Step — of —

incoming i

—

nums[i]

deque size

—

indices held

pops this step

—

back + front

window max

—

deque front

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	nums[i]	pop back	pop front	deque (idx)	emit max

C++ implementation

sliding_window_maximum.cpp

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

// Max of every window of size k, using a monotonic deque of indices
vector<int> maxSlidingWindow(vector<int>& a, int k) {
    deque<int> dq;              // stores indices, a[dq] decreasing
    vector<int> res;

    for (int i = 0; i < (int)a.size(); i++) {
        // drop the front if it has left the window
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();

        // drop smaller values from the back, they can't be a max
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();

        dq.push_back(i);

        // once the first window is complete, front is the max
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

int main() {
    vector<int> a = {1,3,-1,-3,5,3,6,7};
    for (int x : maxSlidingWindow(a, 3)) cout << x << " "; // 3 3 5 5 6 7
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars