DSAPrep
HardSliding Window

Sliding Window Maximum

You are given an array of integers nums. There is a sliding window of size k which is moving 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 sliding window, i.e. the maximum element of every window as it slides across the array.

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. Window [3,-1,-3] -> max 3. Window [-1,-3,5] -> max 5. Window [-3,5,3] -> max 5. Window [5,3,6] -> max 6. Window [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
View original on LeetCode ↗

The brute force recomputes the max of each window from scratch. The key insight for the optimal approach: once a smaller number sits behind a larger number inside the window, that smaller number can never become the max before the larger one leaves the window — so it can be permanently discarded. Keeping only the numbers that could still possibly become the max, in decreasing order, gives a monotonic deque whose front is always the current window’s maximum.

Brute Force

Time O(n · k)Space O(1)

For every window of size k, scan all k elements to find the max.

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        result = []
        for i in range(n - k + 1):
            result.append(max(nums[i:i + k]))
        return result

Why it’s slow: each of the O(n) windows requires an O(k) scan to find its max, and consecutive windows overlap in k - 1 elements — nearly all of that scanning work is repeated for the next window.

Sliding Window (Monotonic Deque)

OptimalTime O(n)Space O(k)

Maintain a deque of indices whose values are strictly decreasing front-to-back. For each new index i: pop from the back while the new value is greater than or equal to the value at the back (those indices can never be the max again while nums[i] is in the window), then append i. Pop from the front if it has fallen outside the window (index <= i - k). Once the window has filled up (i >= k - 1), the value at the front of the deque is the window’s maximum.

from collections import deque


class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        dq = deque()  # stores indices, values strictly decreasing
        result = []
        for i, num in enumerate(nums):
            while dq and nums[dq[-1]] < num:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result

Tracing nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (deque shown as indices’ values, front first):

leftright
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
deque = [1]
1 / 8
comparingseenresultdiscarded

Index 0 enters the deque. Window still filling.

Correctness: an index popped from the back is always dominated by a later, larger value that will outlive it in every window they both could belong to, so it could never have been reported as a max — discarding it loses nothing. An index popped from the front has genuinely left the window. What remains at the front is therefore always the largest value still within the window.

Complexity: each index is pushed onto the deque exactly once and popped at most once (from either end), so the total deque work across the whole array is O(n). The deque holds at most k indices at a time — O(k) space.