Sliding Window Maximum — Monotonic Deque

What does it solve?

Given an array and a window size k, find the maximum element in every contiguous window of size k as it slides from left to right.

A brute-force scan of every window costs O(n·k). A monotonic deque — storing only indices that could still become the max — does it in O(n) total.

The core idea

// keep the deque strictly decreasing in value:
while dq not empty and arr[dq.back] <= arr[i]:
dq.pop_back() // useless now
dq.push_back(i)
if dq.front <= i - k: dq.pop_front() // expired
// front of dq = max of current window

Complexity

Time complexity

O(n)

Each index is pushed and popped from the deque at most once — amortized O(1) per element.

Space complexity

O(k)

The deque never holds more than k indices at a time.

Examples & edge cases

Live animation

Current index In deque (candidate) Front of deque (window max) Popped (smaller, discarded) Expired (slid out of window)

Deque (front → back) — candidates that could still be the max

Current window

—

Window max

—

Deque size

—

Step

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Index	Value	Popped (back)	Expired (front)	Deque after	Window max

C++ implementation

sliding_window_max.cpp

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

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // stores indices, values strictly decreasing front->back
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        // Remove indices from the back whose value can never win
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();

        dq.push_back(i);

        // Remove the front index if it has slid out of the window
        if (dq.front() <= i - k)
            dq.pop_front();

        // Record the max once the window is full
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    auto ans = maxSlidingWindow(nums, k);

    cout << "Window maximums: ";
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars