Sliding Window Maximum

Hard Monotonic Stack Monotonic Stack Original on LeetCode

Sliding Window Maximum is a hard monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (monotonic deque), runs in O(n) time and O(k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan every window) up.

Problem

You get an integer array nums and a window size k. A window of k consecutive elements starts at the left end of the array and slides one position to the right at a time until it reaches the right end.

Return an array holding the maximum of each window position, from left to right.

Examples

Example 1

Input
nums = [4, -2, 6, 1, 0, 3, 8], k = 3
Output
[6, 6, 6, 3, 8]
Why
The windows are [4, -2, 6], [-2, 6, 1], [6, 1, 0], [1, 0, 3] and [0, 3, 8].

Example 2

Input
nums = [9, 7, 5], k = 1
Output
[9, 7, 5]
Why
With k = 1 every window is a single element.

Example 3

Input
nums = [2, 5, 5, 1], k = 4
Output
[5]
Why
One window covers the whole array.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan every window)O(n · k)O(1) extra
Optimal (monotonic deque)O(n)O(k)

1Brute force (scan every window)

TimeO(n · k)n - k + 1 windows, each scanned in O(k).
SpaceO(1) extraOnly the output array besides a few variables.

For each window start, scan its k elements and record the largest.

  1. For i from 0 to n - k, compute the maximum of nums[i .. i + k - 1].
  2. Store it as result[i].
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        for (int i = 0; i + k <= n; i++) {
            int best = nums[i];
            for (int j = i + 1; j < i + k; j++) best = Math.max(best, nums[j]);
            res[i] = best;
        }
        return res;
    }
}

2Optimal (monotonic deque)

TimeO(n)Each index is pushed once and popped at most once.
SpaceO(k)The deque never holds more than k indices.

Keep a deque of indices whose values strictly decrease from front to back. When a new element arrives, pop from the back every index whose value is <= the new one: those can never be a maximum again, because the new element is larger and stays in the window longer. Pop the front if it has slid out of the window. The front is then the maximum of the current window.

  1. For each index i: if the front index is <= i - k, remove it from the front.
  2. While the back value is <= nums[i], remove it from the back. Then push i at the back.
  3. Once i >= k - 1, append nums[front] to the result.
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}

Edge cases to test

  • k = 1: the output is the input
  • k = n: a single maximum
  • Strictly decreasing input, where every element stays a candidate until it leaves the window
  • Strictly increasing input, where each new element replaces all older candidates
  • Duplicate maximums inside one window

Hints

Hint 1

Recomputing each window's maximum from scratch costs O(k) per window. What can you throw away when a new element arrives?

Hint 2

If a newer element is at least as large as an older one, the older one can never be a window maximum again.

Hint 3

Keep a deque of indices whose values are decreasing. The front is the current maximum; drop it when it slides out of the window.

FAQ

What is the best time complexity for Sliding Window Maximum?

Optimal (monotonic deque) runs in O(n) time and O(k) extra space. Each index is pushed once and popped at most once.

Which pattern does Sliding Window Maximum use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.

Is there a brute force solution for Sliding Window Maximum?

Yes. Brute force (scan every window) takes O(n · k) time and O(1) extra space. For each window start, scan its k elements and record the largest.

Which edge cases should I test for Sliding Window Maximum?

k = 1: the output is the input; k = n: a single maximum; Strictly decreasing input, where every element stays a candidate until it leaves the window; Strictly increasing input, where each new element replaces all older candidates; Duplicate maximums inside one window.