Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    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

    Watch how each new number prunes smaller values off the back of the deque, leaving only values that could still become a max, for nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

    nums · window [0..-], k = 3

    L
    1
    0
    3
    1
    -1
    2
    -3
    3
    5
    4
    3
    5
    6
    6
    7
    7

    Deque of indices — front first, values decreasing

    0 indices
    empty

    Output

    none yet
    Popsback: nonefront: none
    1 / 9
    currentcomparingdiscardedseenresult

    Start: the deque is empty and no output has been produced. It will hold indices, front first, with values strictly decreasing.

    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.

    More Sliding Window practice