Sliding Window Maximum

Practice Link

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Naive Approach#

For each window starting position i, scan all k elements in the window [i, i+k-1] to find the maximum. This is simple but redundant — the overlap between consecutive windows is k-1 elements, yet we recompute the maximum from scratch every time. This results in O(n·k) time, which causes a TLE for large inputs.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result;
        for(int i=0;i<=n-k;i++)
        {
            int maxi = INT_MIN;
            for(int j=i;j<=i+k-1;j++)
            {
                maxi = max(maxi, nums[j]);
            }
            result.push_back(maxi);
        }
        return result;
    }
};

Time Complexity: O(n-k)(k) --> TLE

Space Complexity: O(n-k)

Better Approach#

Key Insight#

The naive approach is slow because we re-scan the entire window every time it slides. But most of that work is wasted — if a new element coming into the window is larger than some elements already inside it, those smaller elements can never be the window maximum for any future window (the new element is both larger and more recent). We can throw them away immediately.

This suggests maintaining a data structure that:

1. Always gives us the current maximum in O(1)
2. Automatically discards elements that are out of bounds (slid past the left edge)
3. Automatically discards elements that are useless (smaller than a newer element)

A monotonic deque (double-ended queue storing indices, ordered largest → smallest value) satisfies all three.

The Two Invariants#

Invariant 1 — Window boundary: The front of the deque must always be inside the current window [i-k+1, i]. If dq.front() == i-k, that index has just slid out — pop it.

Invariant 2 — Monotonic order: The deque stores indices in decreasing order of their values. Before pushing i, pop from the back any index whose value is < nums[i]. Those elements are smaller and older — they can never beat nums[i] for any window that includes i.

After both steps, push i onto the back. The front always holds the index of the current window's maximum.

Step-by-step trace — nums = [3, 1, 3, 5, 2, 1, 4], k = 3#

Result: [3, 5, 5, 5, 4] ✓

Why O(n)?#

Each index is pushed once and popped at most once — so even though there's a while loop inside the for loop, the total number of pop operations across the entire run is bounded by n. Overall: O(n) time.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;   // stores indices, values are decreasing front → back
        vector<int> result;

        for (int i = 0; i < (int)nums.size(); i++) {
            // 1. Evict front if it's outside the current window
            if (!dq.empty() && dq.front() == i - k)
                dq.pop_front();

            // 2. Maintain decreasing order — pop smaller elements from back
            while (!dq.empty() && nums[dq.back()] < nums[i])
                dq.pop_back();

            dq.push_back(i);

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

Time Complexity: O(n) — each element pushed and popped at most once

Space Complexity: O(k) — deque holds at most k indices at any time

Follow-up — Range Sum Instead of Range Maximum#

If you needed range sum instead of range maximum, how would your approach change to maintain linear time complexity?

Range sum is actually simpler — you don't need a deque at all.

Sum is reversible. Maximum is not.

When the window slides right, one element enters the right edge and one leaves the left edge. For sum, you can undo the departure by subtracting it:

vector<int> slidingWindowSum(vector<int>& nums, int k) {
    vector<int> result;
    int windowSum = 0;

    for (int i = 0; i < (int)nums.size(); i++) {
        windowSum += nums[i];          // add incoming element

        if (i >= k)
            windowSum -= nums[i - k]; // subtract outgoing element

        if (i >= k - 1)
            result.push_back(windowSum);
    }
    return result;
}

Time: O(n) · Space: O(1) extra

Why can't maximum do the same?

window = [5, 3, 1],  max = 5
slide  → [3, 1, 2],  max = ?

You know 5 left the window — but you can't recover the new max from just that information. You'd have to rescan. That's why the deque is necessary: it remembers all candidates that could still become the max in a future window, not just the current winner.

The general rule: if the aggregation has an inverse operation (sum → subtract, product → divide), a plain running variable works in O(1) space. If it doesn't (max, min, median, GCD), you need a richer structure.