Leetcode - 239. Sliding Window Maximum

Hard

Dec 27, 2025

#sliding-window

239. 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.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

Constraints:

Notes

Intuition

A monotonic decreasing deque maintains potential maximums in order. When a larger element enters, smaller elements can never be the maximum for any future window, so we remove them.

Implementation

Use a deque storing indices. For each new element, pop from the back while the deque's back value is smaller than the current element (they're no longer useful). Add the current index. If the front index is outside the window (l > q[0]), pop it from the front. Once we've processed at least k elements (r + 1 >= k), the front of the deque is the maximum—add it to the result and slide the window.

Edge-cases

The deque stores indices rather than values, which makes it easy to check if elements are still within the window bounds.

Time: O(n) — each element is added and removed from deque at most once
Space: O(k) — deque holds at most k elements

Complexity

Solution

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        ans = []
        l, r = 0, 0

        while r < len(nums):
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r)

            if q and l > q[0]:
                q.popleft()

            if r + 1 >= k:
                ans.append(nums[q[0]])
                l += 1
            r += 1

        return ans
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()