How do you approach Sliding Window Maximum (Monotonic Deque)?

A heap works in O(n log k); we want O(n).

What is the time complexity of Sliding Window Maximum (Monotonic Deque)?

Time complexity: O(n). Space complexity: O(k).

What are common mistakes on Sliding Window Maximum (Monotonic Deque)?

Picking the wrong strictness. > and >= differ only on ties, and ties are where these problems keep their test cases. Not draining the stack after the loop, which drops every element that never found its boundary. Storing values when the answer is a distance, which needs indices.

gitGood.dev

← Back to problems

Sliding Window Maximum (Monotonic Deque)

HardAlgorithms

Description

You are given an array of integers `nums`, and 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 of each window.

Example 1

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

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

Explanation: Window positions: [1 3 -1] -3 5 3 6 7 → 3 1 [3 -1 -3] 5 3 6 7 → 3 1 3 [-1 -3 5] 3 6 7 → 5 1 3 -1 [-3 5 3] 6 7 → 5 1 3 -1 -3 [5 3 6] 7 → 6 1 3 -1 -3 5 [3 6 7] → 7

Example 2

Input: nums = [1], k = 1

Output: [1]

Constraints

- 1 <= nums.length <= 10^5 - -10^4 <= nums[i] <= 10^4 - 1 <= k <= nums.length

Sliding Window Maximum (Monotonic Deque): approach, complexity and pitfalls

A hard monotonic stack problem, graded against 6 test cases (3 of them hidden).

The pattern: Monotonic Stack

A stack kept sorted, for next-greater and largest-rectangle style questions.

Reach for it when you see: "Next greater/smaller element", or a maximum rectangle/area over a histogram.

More Monotonic Stackproblems →

If you are stuck

Show the 3-step hint ladder

A heap works in O(n log k); we want O(n).
Maintain a deque of indices whose values are in decreasing order. The front is always the max of the current window.
When adding a new element, pop from the back any indices with smaller values (they can never be max while the new element is in the window). Pop from the front when an index falls out of the window.

The optimal approach

Show the approach: Monotonic Deque

Maintain a deque of *indices* such that the values `nums[deque]` are strictly decreasing from front to back. The front is the index of the current window's maximum.

For each new index `i`:

1. While the deque's front index `< i - k + 1`, pop front (it has slid out of the window).

2. While the value at the deque's back is `<= nums[i]`, pop back (those values are now dominated and can never be max again).

3. Push `i` to the back.

4. Once `i >= k - 1`, record `nums[deque.front]` as this window's max.

Each index is pushed and popped at most once across the whole run.

Time: O(n)
Space: O(k)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Monotonic Stack mistakes

These apply to the pattern as a whole, not just this problem.

Picking the wrong strictness. `>` and `>=` differ only on ties, and ties are where these problems keep their test cases.
Not draining the stack after the loop, which drops every element that never found its boundary.
Storing values when the answer is a distance, which needs indices.