How do you approach Sliding Window Maximum?

A brute force approach checks all k elements for each window - can you maintain the max more efficiently?

What is the time complexity of Sliding Window Maximum?

Time complexity: O(n) - each element is added and removed at most once. Space complexity: O(k) - deque size.

What are common mistakes on Sliding Window Maximum?

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

HardData Structures

Description

You are given an array of integers `nums` and an integer `k` representing the size of a sliding window which moves 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 value** in each sliding window position.

Example 1

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

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

Explanation: Window [1,3,-1] max=3, [3,-1,-3] max=3, [-1,-3,5] max=5, [-3,5,3] max=5, [5,3,6] max=6, [3,6,7] max=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: 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 brute force approach checks all k elements for each window - can you maintain the max more efficiently?
Use a deque (double-ended queue) to store indices of useful elements.
Remove indices that are out of the window from the front, and remove smaller elements from the back.

The optimal approach

Show the approach: Monotonic Deque

Maintain a deque of indices in decreasing order of their values. For each new element: (1) remove indices that are out of the current window from the front, (2) remove indices of elements smaller than the current element from the back, (3) add the current index. The front of the deque is always the maximum of the current window.

Time: O(n) - each element is added and removed at most once
Space: O(k) - deque size

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.