Sliding Window Maximum
Problem
Given an integer array nums and an integer k, return an array of the maximum values of each sliding window of size k moving from left to right across nums.
- 1 ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
- 1 ≤ k ≤ nums.length
Example
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]The brute-force approach would compute the maximum for each window by scanning all k elements, resulting in O(n*k) time. Instead, the algorithm maintains a deque of indices representing elements in decreasing order of their values. For each new element at index r, it removes indices from the deque's tail whose corresponding values are less than nums[r], ensuring the deque's head always holds the index of the maximum element in the current window. When the left pointer l moves past the deque's head, that index is removed. Once the window size reaches k, the maximum (nums[q[0]]) is appended to the output. This approach achieves O(n) time by ensuring each element is added and removed at most once.
Approach
Straightforward Solution
A naive solution iterates over each window and scans all k elements to find the maximum, resulting in O(n*k) time, which is too slow for large inputs.
Core Observation
The maximum of a sliding window depends on the relative order of elements within that window. Maintaining a data structure that preserves the order of potential maximum candidates allows efficient updates as the window slides.
Path to Optimal
PreviewThe key recognition signals are 'sliding window', 'maximum in each window', and 'efficient updates'…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a deque to store indices of elements in decreasing order of their values. For each new element, pop from the deque's tail while the current element is greater, ensuring the deque's head is always the maximum…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each element is added to and removed from the deque at most once, resulting in linear time relative to the input size.
Space
O(k)
The deque stores at most k indices corresponding to elements in the current window, so auxiliary space scales linearly with the window size.
Pattern Spotlight
Sliding Window (Monotonic Queue)
Maintain a deque of indices in decreasing order of their values to ensure the front always holds the maximum for the current window, discarding smaller elements as new ones arrive and removing indices that fall out of the window.
Solution
| 1 | import collections
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
|
| 5 | output = []
|
| 6 | q = collections.deque()
|
| 7 | l = r = 0
|
| 8 |
|
| 9 | while r < len(nums):
|
| 10 | while q and nums[q[-1]] < nums[r]:
|
| 11 | q.pop()
|
| 12 | q.append(r)
|
| 13 |
|
| 14 | if l > q[0]:
|
| 15 | q.popleft()
|
| 16 |
|
| 17 | if (r + 1) >= k:
|
| 18 | output.append(nums[q[0]])
|
| 19 | l += 1
|
| 20 | r += 1
|
| 21 |
|
| 22 | return output |
Step-by-Step Solution
Initialize Output List, Deque, and Window Pointers
| 5 | output = []
|
| 6 | q = collections.deque()
|
| 7 | l = r = 0
|
Objective
To prepare data structures and pointers for tracking the sliding window and its maximum efficiently.
Key Insight
Initializing an empty output list collects the maximums for each window. The deque will store indices of elements in decreasing order of their values, enabling O(1) access to the current maximum. Two pointers, l and r, represent the left and right boundaries of the sliding window, facilitating window movement and boundary checks.
Interview Quick-Check
Core Logic
The deque stores indices, not values, to efficiently check if elements are out of the current window and to access their values in nums.
State & Boundaries
Both pointers start at 0, representing an empty window that will expand as r moves forward.
Expand Window and Maintain Monotonic Deque
To slide the right pointer forward, updating the deque to maintain decreasing order of values and removing indices of smaller elements.
Remove Out-of-Window Indices from Deque Head
To discard indices from the deque's front that are no longer within the current sliding window boundaries.
Record Maximum and Slide Window Forward
To append the current window's maximum to the output once the window size reaches k and then move the left pointer to slide the window.
Return the List of Sliding Window Maximums
To output the collected maximum values for all sliding windows after processing the entire array.
4 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while q and nums[q[-1]] < nums[r]:While the deque is not empty and the current element is greater than the element at the deque's tail, pop from the tail.
Removing smaller elements from the tail maintains the deque's decreasing order, ensuring the front always holds the maximum candidate for the current window.
output.append(nums[q[0]])Append the value at the deque's front index to the output list as the current window's maximum.
The deque's front always holds the index of the maximum element in the current window, so appending nums[q[0]] records the correct maximum.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why does maintaining a deque of indices in decreasing order of their values guarantee O(n) time complexity?
See the answer with Pro.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Sliding Window Maximum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Sliding Window Maximum drill