What is the brute force approach and complexity for Sliding Window Maximum?

For each of the n − k + 1 windows, scan its k elements for the max with time complexity O(N · K) and space complexity O(1).

What is the optimal approach and complexity for Sliding Window Maximum?

Keep only indices that can still become the max, values decreasing front to back with optimal time complexity O(N) and space complexity O(K).

How do you identify the pattern for Sliding Window Maximum?

Look for key signals in the prompt: "window of size k moves one step at a time" indicates Fixed sliding window — one element enters and one leaves at every step.; "largest value inside the window" indicates The aggregate is a max, which cannot be fixed in O(1) when an element leaves → need a structure that keeps backup candidates.; "at every position" indicates We need the max many times as the window moves, so it must be cheap to read each time..

Sliding Window Maximum

Hard·LeetCode #239Basic Anchor

LeetCode

Jump:

30-Second Mental ModelFixed Sliding Window + Monotonic Decreasing Deque

Complexity:O(N · K)→O(N)

Key Insight

Keep a deque of indices whose values go down from front to back. When a new element arrives, throw away every element at the back that is ≤ it — they can never be the max again. Drop the front when it slides out of the window. The front is always the window max.

Core Validity Invariant

An element is worth keeping only if no element after it in the window is bigger or equal. The window itself is always valid when it has exactly k elements — the deque just answers "what is the max?" in O(1).

Problem

You are given an integer array nums and a number k.

A window of size k starts at the left end of the array and moves one step to the right at a time, until it reaches the right end. At every position, the window covers exactly k neighbouring elements.

Return a list with the largest value inside the window at each position, from left to right.

Input

An integer array nums of length n, and an integer k.

Output

An array of n − k + 1 numbers: the maximum of each window of size k, in order.

Example 1

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Output: [3, 3, 5, 5, 6, 7]

The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]. Their maxima are 3, 3, 5, 5, 6, 7.

Example 2

Input: nums = [1], k = 1

Output: [1]

There is only one window and it holds just 1.

Example 3

Input: nums = [9, 10, 9, -7, -4, -8, 2, -6], k = 5

Output: [10, 10, 9, 2]

When the 10 slides out, the next biggest value 9 takes over. When that 9 slides out too, the max drops all the way to 2.

Constraints

• 1 ≤ n ≤ 10^5
• −10^4 ≤ nums[i] ≤ 10^4
• 1 ≤ k ≤ n

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Is the window size fixed or does it change?
2.
When the window moves one step, which element enters and which one leaves?
3.
If I know the max of the current window and the max element leaves, do I know the new max?
4.
If a big number arrives, is there any reason to keep remembering the smaller numbers that came before it?
5.
What would I need to store so that the "next max" is ready the moment the current max leaves?

Brute force approach

Idea

There are n − k + 1 windows. For each one, loop over its k elements and keep the largest. Add it to the answer.

Thinking process

1
A window is decided by where it starts, from 0 to n − k.
2
For each start, look at all k elements and take the biggest.
3
Push that biggest value into the result list.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;

        // Try every window start.
        for (int start = 0; start + k <= n; start++) {
            // Scan all k elements of this window from scratch.
            int best = nums[start];
            for (int i = start + 1; i < start + k; i++) {
                best = max(best, nums[i]);
            }
            res.push_back(best);
        }
        return res;
    }
};

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];

        // Try every window start.
        for (int start = 0; start + k <= n; start++) {
            // Scan all k elements of this window from scratch.
            int best = nums[start];
            for (int i = start + 1; i < start + k; i++) {
                best = Math.max(best, nums[i]);
            }
            res[start] = best;
        }
        return res;
    }
}

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        res: list[int] = []

        # Try every window start.
        for start in range(n - k + 1):
            # Scan all k elements of this window from scratch.
            best = nums[start]
            for i in range(start + 1, start + k):
                best = max(best, nums[i])
            res.append(best)

        return res

export function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const res: number[] = [];

    // Try every window start.
    for (let start = 0; start + k <= n; start++) {
        // Scan all k elements of this window from scratch.
        let best = nums[start];
        for (let i = start + 1; i < start + k; i++) {
            best = Math.max(best, nums[i]);
        }
        res.push(best);
    }
    return res;
}

Complexity

Time O(N · K)Space O(1)

With n = 10^5 and k = 5·10^4, that is about 2.5·10^9 comparisons — too slow. Only O(1) extra memory besides the output.

Better approach

Why brute force is slow

Every window is scanned from scratch, even though two neighbouring windows share k − 1 elements.

What repeated work are we doing?

The same elements are compared again and again, once for every window that contains them — up to k times each.

What information can we reuse?

Keep the window's values in a sorted structure that survives from one window to the next. Then each move only costs one insert and one erase.

New approach

Idea

Keep all k values of the current window in a multiset, which stays sorted. When the window moves, insert the new value and erase one copy of the value that left. The max is *window.rbegin().

Thinking process

1
Brute force rescans the k − 1 elements that the old and new window share.
2
I want a container that can add a value, remove a value, and tell me the biggest, all quickly.
3
A balanced tree does all three in O(log k). In C++ that is multiset (a multiset, because values can repeat).
4
Each step: insert the entering value, erase the leaving one, read the last element.

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        // Holds exactly the k values of the current window, kept sorted.
        // A multiset (not a set) because values can repeat.
        multiset<int> window;

        for (int right = 0; right < n; right++) {
            window.insert(nums[right]);                    // enters
            if (right >= k) {
                // Erase ONE copy of the value that left, not all copies.
                window.erase(window.find(nums[right - k]));
            }
            if (right >= k - 1) {
                res.push_back(*window.rbegin());           // largest value
            }
        }
        return res;
    }
};

import java.util.TreeMap;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        // Holds the values of the current window and their frequencies, kept sorted.
        TreeMap<Integer, Integer> window = new TreeMap<>();

        for (int right = 0; right < n; right++) {
            window.put(nums[right], window.getOrDefault(nums[right], 0) + 1); // enters
            if (right >= k) {
                // Erase ONE copy of the value that left.
                int leftVal = nums[right - k];
                int c = window.get(leftVal);
                if (c == 1) window.remove(leftVal);
                else window.put(leftVal, c - 1);
            }
            if (right >= k - 1) {
                res[right - k + 1] = window.lastKey(); // largest value
            }
        }
        return res;
    }
}

import heapq

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        res: list[int] = []
        # Max-heap storing (-value, index) for lazy deletion.
        heap: list[tuple[int, int]] = []

        for right in range(n):
            heapq.heappush(heap, (-nums[right], right))

            if right >= k - 1:
                # Remove elements that fell out of the window.
                while heap and heap[0][1] <= right - k:
                    heapq.heappop(heap)
                res.append(-heap[0][0])

        return res

function binarySearch(arr: number[], target: number): number {
    let low = 0, high = arr.length;
    while (low < high) {
        const mid = (low + high) >> 1;
        if (arr[mid] >= target) high = mid;
        else low = mid + 1;
    }
    return low;
}

export function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const res: number[] = [];
    // Sorted array of values currently in the window.
    const window: number[] = [];

    for (let right = 0; right < n; right++) {
        // Insert nums[right] in sorted order.
        const inIdx = binarySearch(window, nums[right]);
        window.splice(inIdx, 0, nums[right]);

        if (right >= k) {
            // Remove one copy of the value leaving the window.
            const outIdx = binarySearch(window, nums[right - k]);
            window.splice(outIdx, 1);
        }

        if (right >= k - 1) {
            // The maximum is the last element of the sorted window.
            res.push(window[window.length - 1]);
        }
    }
    return res;
}

Complexity

Time O(N log K)Space O(K)

Fast enough to pass. But the tree keeps every value sorted, which is more than we need — we only ever ask for the max. A simpler structure can do it in O(1) per step on average.

A max-heap of (value, index) pairs also works: push each element, and before reading the top, pop it while its index has left the window ("lazy removal"). That is O(N log N), because old elements can pile up in the heap.

Optimized approach

Idea

Visual

Green = still in the deque. Orange = thrown away because a newer, bigger (or equal) value arrived. Red = slid out of the window.

Why elements are thrown awaynums = [9, 10, 9, -7, -4, -8, 2, -6], k = 5step 1/8

nums

-7

-4

-8

-6

▲L R

Still useful (deque)

0:9

Thrown away (value ← beaten by)

[ ]

0 thrown away this step

Nothing is smaller than 9 at the back, so nothing is thrown away.

Start from brute force

Brute force rescans all k elements of each window to find its max, then moves one step and rescans almost the same elements.

Find the repeated work

Neighbouring windows share k − 1 elements, so most comparisons are repeated. But we can't just keep one max variable: when the max leaves, we need to know the next biggest instantly. So we keep a short list of backup candidates — and throw out anything that can never win.

Define the state — what variables do I need?

dq: Deque of indices inside the current window. Their values strictly decrease from front to back. These are the only elements that could still be a window max.
right: Index of the element that just entered. The window is [right − k + 1 … right].
res: The answer list. One max is added for each full window.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

A new element nums[right] arrives

while (nums[dq.back()] <= nums[right]) dq.pop_back(); then dq.push_back(right)

Each popped element is smaller than or equal to nums[right] and leaves the window before it. So for every future window that contains the popped element, nums[right] is also there and is at least as big. The popped element can never be the answer.

The front index is ≤ right − k

dq.pop_front()

That index is no longer inside the window [right − k + 1 … right]. Only the front can be this old, because indices in the deque are in increasing order.

right ≥ k − 1 (a full window exists)

res.push_back(nums[dq.front()])

Values decrease from front to back, so the front holds the largest value still in the window.

What does the current window add to the answer?

Each full window adds exactly one number to the answer: the value at the front of the deque.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        // dq stores INDICES. Their values decrease from front to back,
        // so the front is always the max of the window.
        deque<int> dq;

        for (int right = 0; right < n; right++) {
            // nums[right] is newer and at least as big as these elements,
            // so they can never be the max again. Throw them away.
            while (!dq.empty() && nums[dq.back()] <= nums[right]) {
                dq.pop_back();
            }
            dq.push_back(right);

            // The front index fell out of the window [right-k+1 .. right].
            if (dq.front() <= right - k) {
                dq.pop_front();
            }

            // Once the first full window is formed, record its max.
            if (right >= k - 1) {
                res.push_back(nums[dq.front()]);
            }
        }
        return res;
    }
};

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        // dq stores INDICES. Their values decrease from front to back,
        // so the front is always the max of the window.
        Deque<Integer> dq = new ArrayDeque<>();

        for (int right = 0; right < n; right++) {
            // nums[right] is newer and at least as big as these elements,
            // so they can never be the max again. Throw them away.
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[right]) {
                dq.pollLast();
            }
            dq.offerLast(right);

            // The front index fell out of the window [right-k+1 .. right].
            if (dq.peekFirst() <= right - k) {
                dq.pollFirst();
            }

            // Once the first full window is formed, record its max.
            if (right >= k - 1) {
                res[right - k + 1] = nums[dq.peekFirst()];
            }
        }
        return res;
    }
}

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        res: list[int] = []
        # dq stores INDICES. Their values decrease from front to back,
        # so the front is always the max of the window.
        dq: deque[int] = deque()

        for right in range(n):
            while dq and nums[dq[-1]] <= nums[right]:
                dq.pop()
            dq.append(right)

            if dq[0] <= right - k:
                dq.popleft()

            if right >= k - 1:
                res.append(nums[dq[0]])

        return res

export function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const res: number[] = [];
    // dq stores INDICES. Their values decrease from front to back,
    // so the front is always the max of the window.
    const dq: number[] = [];

    for (let right = 0; right < n; right++) {
        while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[right]) {
            dq.pop();
        }
        dq.push(right);

        if (dq[0] <= right - k) {
            dq.shift();
        }

        if (right >= k - 1) {
            res.push(nums[dq[0]]);
        }
    }
    return res;
}

Complexity

Time O(N)Space O(K)

The while loop inside the for loop looks like O(N · K), but it is not. Every index is pushed once and popped at most once, so all the pops added together are at most n. Total work is O(N). This is called amortised O(1) per step.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each of the n − k + 1 windows, scan its k elements for the max	O(N · K)	O(1)
Better	Keep the window's values in a multiset; the largest is at the end	O(N log K)	O(K)
Optimal	Keep only indices that can still become the max, values decreasing front to back	O(N)	O(K)

Why does this belong to this pattern?

Clues in the problem statement

“window of size k moves one step at a time”Fixed sliding window — one element enters and one leaves at every step.
“largest value inside the window”The aggregate is a max, which cannot be fixed in O(1) when an element leaves → need a structure that keeps backup candidates.
“at every position”We need the max many times as the window moves, so it must be cheap to read each time.

Contiguous range+fixed size k+max of the window at every step→Fixed Sliding Window + Monotonic Decreasing Deque

This is the anchor problem for the deque sub-pattern. The window part is easy (fixed size). The new idea is the deque that throws away elements that can never be the max again. The next questions in this sub-pattern reuse the same deque, but inside a variable window, where the max (and min) decide whether the window is valid.

Don't make this mistake

Storing values instead of indices

✗ dq.push_back(nums[right]);

✓ dq.push_back(right);

With only values, you can't tell when the front has slid out of the window. Store indices and read the value with nums[i].

Popping the front by value instead of by position

✗ if (nums[dq.front()] == nums[right - k]) dq.pop_front();

✓ if (dq.front() <= right - k) dq.pop_front();

Comparing values breaks when values repeat. Compare the index with the window's left edge.

Erasing a value from a multiset with erase(value)

✗ window.erase(nums[right - k]);

✓ window.erase(window.find(nums[right - k]));

erase(value) removes every copy of that value. You only want to remove the one copy that left the window.

Thinking you need a sum-style O(1) update

Pattern confusion: in Max Sum Subarray of Size K you can keep one running sum. A max does not work that way — if the max leaves, a single variable can't tell you the next one. Whenever the window aggregate is a max or min, reach for the monotonic deque, not a single variable.

Assuming the inner while loop makes it O(N · K)

Count pops, not loops. Each index is pushed once and popped at most once over the whole run, so the total number of pops is at most n.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Longest Continuous Subarray With Absolute Diff ≤ Limit