Given an integer array nums and a window size k, a window of k consecutive elements slides from the left end of the array to the right, one position at a time.
Return an array of the maximum value in each window position, in order from left to right.
Example
The max of each of the six windows of width 3, slid left to right.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= k <= nums.length
- -10^4 <= nums[i] <= 10^4
Intuition
The direct approach slides a window of width k across the array and, at each position, takes the max of the k values inside it.
function maxSlidingWindow(nums, k) {
const result = [];
// Each window starts at i and spans k elements.
for (let i = 0; i + k <= nums.length; i++) {
let m = nums[i];
for (let j = i + 1; j < i + k; j++) m = Math.max(m, nums[j]); // rescan the window
result.push(m);
}
return result;
}Re-maxing all k values for each of the ~n windows is O(n·k) — quadratic when k grows with n. A heap drops it to O(n log k); a monotonic deque reaches O(n). Can we do better than the heap?
The key observation: if an earlier value is ≤ a later value that's still in the window, the earlier one can never be a future maximum — it's dominated and dead. So keep a double-ended queue of indices whose values strictly decrease front→back; the front is always the current window's max. This is the deque cousin of the [monotonic stack](/study-guide/algos/topic/stacks), with one extra move: evict the front when it slides out of the window.
For each i: pop dominated values off the back (nums[back] ≤ nums[i]), push i, drop the front if it's ≤ i - k, and once the first window is full read the front. The lane below shows the array; range is the current window and the caption tracks the deque (front listed first). Walking it through:
nums = [1, 3, -1, -3, 5, 3], k = 3
Building the first window: 3 dominated the earlier 1 (popped). Deque indices: [1, 2]. First max = 3.
-3 doesn't dominate anyone, just appended. Deque: [1, 2, 3]. Front index 1 (value 3) is the max.
Value 5 dominates everything waiting and clears the deque; index 1 also slid past the window. Deque: [4]. Max = 5.
3 can't dominate the 5 ahead of it, so it just appends. Deque: [4, 5]. Front index 4 (value 5) is the max.
Four windows, four maxima. Each index entered and left the deque once, so the whole pass is O(n).
Optimization
Monotonic decreasing deque
A heap of window values would be O(n log k); a monotonic deque does it in O(n). Keep a deque of indices whose values are strictly decreasing from front to back, so the front index always holds the current window's maximum.
For each new index i: pop indices off the back while their value is <= nums[i] (they can never be the max while nums[i] is in the window, so they're dead weight), then push i. Pop the front index if it has slid out of the window (<= i - k). Once the first full window is formed (i >= k - 1), the value at the front index is that window's maximum.
Each index is pushed and popped at most once, so O(n) time, O(k) space for the deque.
function maxSlidingWindow(nums, k) {
const result = [];
const deque = []; // indices, values strictly decreasing front -> back
for (let i = 0; i < nums.length; i++) {
// Drop smaller-or-equal values from the back: they can't be a future max.
while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
// Drop the front if it has slid out of the window.
if (deque[0] <= i - k) deque.shift();
// Once the first window is full, record the front (the window max).
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
}Complexity analysis
Time complexity: O(n). Here's why:
- The loop visits each index once.
- Each index is pushed onto the deque once and removed once (from either end), so the back-eviction
whileis amortized O(1) per step.
So the total is O(n), where n is the array length — beating both the O(n·k) brute force and the O(n log k) heap approach.
Space complexity: O(k). Here's why:
- The deque only holds indices currently inside the window.
- At most
kindices fit in a window, so the deque never exceedskentries.
So the auxiliary space is O(k). The output array of window maxima is the required result, not counted.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [3], k = 1 | [3] | Single element, window of 1 — the element itself. |
| nums = [7,2,4], k = 2 | [7,4] | Two windows: max(7,2)=7, max(2,4)=4. |
| nums = [9,11], k = 2 | [11] | Window equals the array — one max. |
| nums = [6,5,4,3,2], k = 3 | [6,5,4] | Decreasing — each window's max is its left edge. |
| nums = [2,4,6,8], k = 2 | [4,6,8] | Increasing — each window's max is its right edge. |
| nums = [1,3,-1,-3,5,3,6,7], k = 3 | [3,3,5,5,6,7] | The example — a value can dominate several earlier ones at once. |
Try it yourself
Write your solution against the real judge before checking the reference.