HardArrayQueueSliding WindowHeap (Priority Queue)Monotonic Queue

Sliding Window Maximum

1 approach, code in every language

You are given an integer array nums and an integer k. Imagine a window of width k that starts at the leftmost end of the array and slides one position to the right at a time until it reaches the far end.

At every stopping point the window covers exactly k consecutive elements, and you can only see the values currently inside it. For each window position, determine the largest value it contains.

Return these maximums as an array, ordered from the first window to the last.

Example 1

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

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

Window [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5, [-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7.

Example 2

Input: nums = [1], k = 1

Output: [1]

A single element forms the only window, so its maximum is itself.

Constraints

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

Monotonic Decreasing Deque

Keep a deque of indices whose values are strictly decreasing so the window maximum is always at the front.

Loading animation…

Intuition

A brute-force scan of every window costs O(n*k) because it re-examines overlapping elements. The key observation is that if a newer element is greater than or equal to older elements still inside the window, those older elements can never be the maximum again and are safe to discard. We store indices in a deque and keep the corresponding values in decreasing order from front to back. That way the front always holds the index of the current window's maximum, and each index is pushed and popped at most once. The window boundary is enforced by evicting the front when its index falls outside the current range.

Algorithm walkthrough

1Create an empty deque that will hold array indices, and an empty result list.
2For each index i, pop indices from the back while nums at the back is less than or equal to nums[i]; those values can no longer be a maximum.
3Push the current index i onto the back of the deque.
4If the front index is out of the window (front <= i - k), remove it from the front.
5Once i reaches k - 1, the first full window exists, so append nums at the front index to the result.
6Return the result list after the loop finishes.

Implementation

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # stores indices; values are decreasing front-to-back
        result = []
        for i, num in enumerate(nums):
            # Drop smaller-or-equal values from the back
            while dq and nums[dq[-1]] <= num:
                dq.pop()
            dq.append(i)
            # Drop the front if it slid out of the window
            if dq[0] <= i - k:
                dq.popleft()
            # Record the max once the first window is complete
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result

Time

O(n)

Space

O(k)

Each index is added and removed from the deque at most once, so the amortized cost per element is constant. The deque never holds more than k indices.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Rolling Peak Readings is our own problem on the technique behind Sliding Window Maximum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free