Sliding Window Maximum

Q: What is the time complexity of Sliding Window Maximum?

The monotonic deque solution runs in O(n) time. Every index is pushed once and popped at most once, so the inner loop does at most n pops over the whole run, even though a single step can pop several. The deque holds at most k indices, so the extra space is O(k) on top of the result.

HardSliding window Monotonic stack Queue

+10

You get an array of integers nums and a window size k. A window covers k consecutive values. It starts at the left end of the array and moves one position to the right at a time, until its right edge sits on the last value.

Return an array with the largest value inside the window at each of its positions, from left to right. An array of length n has n-k+1 windows, so the result has n-k+1 values.

Function

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: the array the window slides over
kinteger: the number of values in every window
Returnsinteger-array: the largest value of each window, from the leftmost window to the rightmost

Constraints

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
The result holds nums.length-k+1 values, one per window, in order from left to right.

Examples

Input: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Output: [12, 12, 12, 8, 8]
Explanation: 12 sits inside the first three windows, [4, 2, 12], [2, 12, 3] and [12, 3, 8]. After it slides out, the windows [3, 8, 5] and [8, 5, 1] both have 8 as their largest value.

Input: nums = [-3, -1, -7, -2]k = 2
Output: [-1, -1, -2]
Explanation: The windows are [-3, -1], [-1, -7] and [-7, -2]. The largest of two negative numbers is the one closer to zero, which gives -1, -1 and -2.

Input: nums = [6, 6, 1]k = 3
Output: [6]
Explanation: When k equals the length of the array there is one window, the whole array. Its largest value is 6, and the second copy of 6 does not add a second answer.

+15 hidden tests on Submit

Follow-up

Can you build a queue that supports adding a value at the back, removing the value at the front and reading its current maximum, each in O(1) amortized time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Neighbouring windows share k-1 values, so computing each maximum from scratch repeats almost all the work. The hard part is that a maximum cannot be undone: when the largest value slides out on the left, you need the next largest without reading the window again. A monotonic deque keeps exactly the values that could still become a maximum, in order, so the answer is always at its front and every index enters and leaves it once.

Scan every window

Correct, but does not finish on the largest tests

Intuition

The most direct idea follows the statement. The window that starts at index start covers start to start+k-1. Read those k values, keep the largest, and move the start one step to the right. There are n-k+1 starts, from 0 to n-k.

It is correct by definition: every window is read in full, so its largest value cannot be missed. The extra memory is one variable for the running maximum, apart from the result.

It is slow. Each of the n-k+1 windows costs k reads, and the product is largest when k is about half of n. With n = 2 × 10^4 and k = 10^4 that is 10^4 windows of 10^4 values, or 10^8 reads. Worse, two neighbouring windows share k-1 values, so nearly every read repeats one you already made.

Algorithm

Create an empty result list.
Loop start from 0 to n-k.
Set best to nums[start], then compare it with every value up to nums[start+k-1] and keep the larger one.
Append best to the result.
Return the result.

def maxSlidingWindow(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        # Read all k values of this window again
        result.append(max(nums[i] for i in range(start, start + k)))
    return result

Blocks with maxima from each side

Intuition

Cut the array into blocks of k: indices 0 to k-1, then k to 2k-1, and so on, with a shorter last block if n is not a multiple of k. A window is exactly k long, so it either matches one block or covers the end of one block and the start of the next. It never touches three blocks.

That suggests two arrays. fromStart[i] is the largest value from the start of i's block up to i, filled left to right and reset at every block start. toEnd[i] is the largest value from i to the end of its block, filled right to left and reset at every block end. The window starting at i ends at i+k-1. Its left part is covered by toEnd[i] and its right part by fromStart[i+k-1], so its maximum is the larger of the two. When the window is a whole block, both halves are that block's maximum, and the answer is still right.

With nums = [4, 2, 12, 3, 8, 5, 1] and k = 3, the blocks are [4, 2, 12], [3, 8, 5] and [1]. fromStart is [4, 4, 12, 3, 8, 8, 1] and toEnd is [12, 12, 12, 8, 8, 5, 1]. The window [2, 12, 3] starts at 1: toEnd[1] = 12 covers 2 and 12, fromStart[3] = 3 covers 3, and the answer is 12.

This runs in O(n) time, three passes over the array. The cost is two helper arrays of length n, and it needs the whole array before it can answer the first window.

Algorithm

Fill fromStart left to right: copy nums[i] when i is a multiple of k, otherwise take the larger of fromStart[i-1] and nums[i].
Fill toEnd right to left: copy nums[i] when i is the last index or i+1 is a multiple of k, otherwise take the larger of toEnd[i+1] and nums[i].
For every start i from 0 to n-k, append the larger of toEnd[i] and fromStart[i+k-1].
Return the result.

def maxSlidingWindow(nums, k):
    n = len(nums)
    # Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
    from_start = [0] * n  # max from the start of i's block up to i
    to_end = [0] * n      # max from i up to the end of i's block
    for i in range(n):
        if i % k == 0:
            from_start[i] = nums[i]
        else:
            from_start[i] = max(from_start[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            to_end[i] = nums[i]
        else:
            to_end[i] = max(to_end[i + 1], nums[i])
    # A window [i, i+k-1] is the tail of one block plus the head of the next.
    return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]

Monotonic deque of indices

Intuition

Start from one observation. Suppose index j comes before index i and nums[j] ≤ nums[i]. Every later window that still holds j also holds i, because i is further right and leaves later. In all of those windows nums[i] is at least as big, so j can never be the maximum again. The moment i arrives, j is useless and you can forget it.

Keep a double-ended queue of the indices you have not forgotten. When i arrives, pop indices off the back while their values are at most nums[i], then push i. The survivors then have strictly decreasing values from front to back, since any older value that was not bigger would have been popped. So the front holds the largest value in the window. The deque stores indices, not values, because the front also has to leave when the window passes it: the window that ends at i starts at i-k+1, so index i-k is the one that has slid out, and if it is at the front you drop it.

Follow nums = [4, 2, 12, 3, 8, 5, 1] with k = 3, listing values in the deque. 4 enters: [4]. 2 is smaller, so it waits behind it: [4, 2]. 12 pops both: [12], and the first window's answer is 12. 3 waits: [12, 3], answer 12. 8 pops 3: [12, 8], answer 12. 5 waits: [12, 8, 5], but 12 sits at index 2, and the window that ends at index 5 starts at index 3, so 12 has slid out: [8, 5], answer 8. 1 waits: [8, 5, 1], answer 8.

Why this is O(n): the inner loop can pop several indices on one step, but every index is pushed once and popped at most once, from the back when a bigger value beats it or from the front when it slides out. All the pops of the whole run add up to at most n, so the total work is at most 2n deque operations. Every index in the deque lies inside the current window, so it never holds more than k of them.

Algorithm

Create an empty deque for indices and an empty result list.
For each index i, pop indices off the back while the deque is not empty and the value at its back is at most nums[i].
Push i at the back.
If the index at the front equals i-k, it has left the window: pop it from the front.
Once i ≥ k-1, a full window ends at i: append the value at the front index to the result.
Return the result.

from collections import deque


def maxSlidingWindow(nums, k):
    window = deque()  # indices; their values strictly decrease from front to back
    result = []
    for i, x in enumerate(nums):
        # A value at the back that is not bigger than x can never be a maximum again.
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        # The front index has slid out of the window on the left.
        if window[0] == i - k:
            window.popleft()
        # From index k-1 on, every step completes a window; its maximum sits at the front.
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

Pitfalls and edge cases

Most bugs come from the window's edges or from what the deque stores.

Storing values instead of indices. You then expire the front when it equals nums[i-k], and duplicates break it. With [3, 1, 3] and k = 2, the second 3 pops the first one and is then removed itself, because it equals the value that left. Store indices and compare the front with i-k.
Answering too early or too late. The first full window ends at index k-1, not at k, and the result must hold exactly n-k+1 values.
Expiring the wrong index. The window that ends at i starts at i-k+1, so i-k is the index that leaves. Dropping i-k+1 removes a value still in the window.
Reading the back or the front of an empty deque. Check that it holds something before you compare with its back.
Treating the deque as a copy of the window. It holds only the candidates, anywhere from 1 to k indices, so its size tells you nothing about the window.
In the block approach, forgetting that the last block can be shorter than k. The right to left pass must restart at the last index as well as at every block end.

Frequently asked questions4

What is the time complexity of Sliding Window Maximum?

The monotonic deque solution runs in O(n) time. Every index is pushed once and popped at most once, so the inner loop does at most n pops over the whole run, even though a single step can pop several. The deque holds at most k indices, so the extra space is O(k) on top of the result.

Can Sliding Window Maximum be solved with a heap?

Yes. Push pairs of value and index into a max heap. Before reading the top, pop it while its index is outside the window, since stale entries are removed only when they reach the top. That runs in O(n log n) time and can hold up to n entries. The deque is faster and smaller because it removes useless values as soon as a bigger one arrives.

Why does the deque store indices and not values?

The front must leave when the window moves past it, and only its index tells you that. With values alone you would have to guess from nums[i-k], which fails when the same value appears more than once. The index also gives you the value at no cost, as nums[index].

What is the difference between a monotonic deque and a monotonic stack?

The back of the deque works like a monotonic stack: before you push a value, you pop the ones it makes useless. The deque adds a second exit at the front for values that are too old. A problem with no expiry, such as finding the next greater element, needs only the stack; a sliding window needs both ends. Flip the comparison and the same code gives the minimum of every window.

Python

def maxSlidingWindow(nums, k):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

Expected

[12, 12, 12, 8, 8]

Sliding Window Maximum

Function

Constraints

Examples

Hints

Solution

Scan every window

Blocks with maxima from each side

Monotonic deque of indices

Pitfalls and edge cases

Frequently asked questions4

Similar problems