Sliding Window Maximum

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

The monotonic deque solution runs in O(n) time, because every index is pushed once and popped at most once. 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 of k consecutive values starts at the left end and moves right one position at a time, until its right edge sits on the last value. Return the largest value in the window at each position, from left to right: n-k+1 values for an array of length n.

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 is inside the first three windows, so each of them answers 12. After it slides out, [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 array's length there is one window, the whole array. Its largest value is 6; the second copy of 6 adds no second answer.

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 recomputing each maximum repeats almost all the work. But a maximum cannot be undone: when the largest value slides out, you need the next largest without reading the window again. A monotonic deque keeps only the values that could still become a maximum, with the answer at its front.

Scan every window

Correct, but does not finish on the largest tests

Intuition

Read the k values of each window and keep the largest. Every window is read in full, so its maximum cannot be missed. Each of the n-k+1 windows costs k reads, worst when k is about half of n: n = 2 × 10^4 and k = 10^4 give about 10^4 windows of 10^4 values, 10^8 reads.

Algorithm

Loop start from 0 to n-k.
Take the largest of nums[start] through nums[start+k-1].
Append it to the result, and return the result after the loop.

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 k does not divide n. A window is exactly k long, so it is one whole block or the end of one block plus the start of the next.

So precompute fromStart[i], the largest value from the start of i's block up to i, and toEnd[i], the largest from i to the end of its block. The window starting at i ends at i+k-1: toEnd[i] covers its left part and fromStart[i+k-1] its right part, so the larger is its maximum. In the first example the window [2, 12, 3] takes toEnd[1] = 12 and fromStart[3] = 3, giving 12.

Three passes give O(n) time, at the cost of two helper arrays of length n and needing the whole array before the first answer.

Algorithm

Fill fromStart left to right, restarting with nums[i] when i is a multiple of k.
Fill toEnd right to left, restarting with nums[i] at the last index and wherever i+1 is a multiple of k.
For every start i from 0 to n-k, append the larger of toEnd[i] and fromStart[i+k-1].

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

If index j comes before i and nums[j] ≤ nums[i], then j can never be a maximum again: every later window that holds j also holds i, which leaves later. So when i arrives, you can forget j.

Keep a deque of the indices not yet forgotten. When i arrives, pop indices off the back while their values are at most nums[i], then push i. The values left decrease strictly from front to back, so the front is the window's maximum. Store indices, because the front must also leave once the window passes it. In the first example, at index 5 the deque holds 12, 8 and 5; 12 sits at index 5 - 3 = 2, so it leaves and the answer is 8.

Every index is pushed once and popped at most once: at most 2n deque operations, O(n) time. The deque never holds more than k indices.

Algorithm

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 front index equals i-k, it has left the window: pop it.
Once i ≥ k-1, append the value at the front index to 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

Storing values instead of indices. With [3, 1, 3] and k = 2, the second 3 pops the first, then is removed itself because it equals nums[0], the value that left.
Answering too early or too late. The first full window ends at index k-1, and the result must hold exactly n-k+1 values.
Expiring i-k+1 instead of i-k. That index is still the window's first value.
Reading the back of the deque without checking that it holds something.
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 questions3

What is the time complexity of Sliding Window Maximum?

The monotonic deque solution runs in O(n) time, because every index is pushed once and popped at most once. 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, and before reading the top, pop it while its index is outside the window. That runs in O(n log n) time and can hold up to n entries. The deque is faster and smaller because it drops useless values as soon as a bigger one arrives.

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 front exit for values that are too old. Next greater element has no expiry, so it needs only the stack. Flip the comparison and the deque gives every window's minimum.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

[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 questions3

Similar problems