Sliding Window Maximum
Report the largest value in every window of size k as it slides across an array, in O(n) time, using a queue that keeps only useful candidates.
Updated Medium read: 8 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n·k) | O(1) |
| Queue of candidates in decreasing order | O(n) | O(n) |
The problem
Given an array of numbers and a window size k, a window covering k consecutive elements starts at the left edge and moves one place to the right at a time. Return the largest value in the window at each position.
numbers = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]
Window Largest
[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] 7An array of n elements has n − k + 1 windows. The space figures below do not count the array of results that is returned.
Approach 1: brute force
Scan each window for its largest value.
JavaScript
function maxSlidingWindowBruteForce(numbers, k) {
const result = [];
for (let start = 0; start + k <= numbers.length; start++) {
let largest = numbers[start];
for (let i = start + 1; i < start + k; i++) {
largest = Math.max(largest, numbers[i]);
}
result.push(largest);
}
return result;
}Python
def max_sliding_window_brute_force(numbers, k):
result = []
for start in range(len(numbers) - k + 1):
largest = numbers[start]
for i in range(start + 1, start + k):
largest = max(largest, numbers[i])
result.append(largest)
return resultTime O(n·k): about n windows, k elements each. Space O(1). When k is close to half of n, this is as bad as O(n²).
Why the usual window trick is not enough
In Maximum Sum Subarray of Size K, moving the window is cheap because a sum can be undone: add the number that enters, subtract the one that leaves.
A maximum cannot be undone. If the number leaving the window was the maximum, a single stored value says nothing about what the next largest is. Something has to remember the runners-up.
Which numbers are worth remembering
Not all of them. Suppose the window holds 3 and then, further right, 5. From now on the 3 can never be the answer: the 5 is larger, and it will stay in the window longer because it arrived later. The 3 can be forgotten the moment the 5 appears.
So when a new number arrives, every earlier number that is smaller than or equal to it can be thrown away. What survives is a list of candidates in which each one is smaller than the one before it:
- The front is the largest value in the window: the current answer.
- Each candidate behind it is the value that would take over once everything ahead of it has slid out.
Approach 2: a queue of candidates
Keep the candidates in a queue, storing indexes into the array, not values. The index is what reveals when a candidate has slid out of the window. Candidates are added and removed at the back, and removed at the front, which makes this a double-ended queue; the plain queue only removes from the front.
For each new position end:
- If the index at the front is no longer inside the window, remove it.
- Remove indexes from the back while the numbers they point to are less than or equal to the new number.
- Add
endat the back. - If a full window has been seen, the number at the front index is that window's maximum.
JavaScript
function maxSlidingWindow(numbers, k) {
const result = [];
const candidates = []; // indexes whose values run from largest to smallest
let head = 0; // where the front of the queue is inside `candidates`
for (let end = 0; end < numbers.length; end++) {
// 1. The front has slid out of the window.
if (head < candidates.length && candidates[head] <= end - k) head++;
// 2. Candidates the new number beats will never be the answer.
while (
candidates.length > head &&
numbers[candidates[candidates.length - 1]] <= numbers[end]
) {
candidates.pop();
}
// 3. The new number is always a candidate.
candidates.push(end);
// 4. Report once the first full window exists.
if (end >= k - 1) result.push(numbers[candidates[head]]);
}
return result;
}Python
from collections import deque
def max_sliding_window(numbers, k):
result = []
# Indexes whose values run from largest to smallest.
# A deque removes from either end in constant time.
candidates = deque()
for end, value in enumerate(numbers):
# 1. The front has slid out of the window.
if candidates and candidates[0] <= end - k:
candidates.popleft()
# 2. Candidates the new number beats will never be the answer.
while candidates and numbers[candidates[-1]] <= value:
candidates.pop()
# 3. The new number is always a candidate.
candidates.append(end)
# 4. Report once the first full window exists.
if end >= k - 1:
result.append(numbers[candidates[0]])
return resultThe front is removed by moving head forwards instead of calling shift(). In JavaScript, shift() on an array may move every remaining element down one place, which would quietly bring back the cost this approach is meant to remove.
Walkthrough
numbers = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. The queue is shown as values for readability; the code stores their indexes.
| end (value) | Removed from front | Removed from back | Queue after | Output |
|---|---|---|---|---|
| 0 (1) | 1 | |||
| 1 (3) | 1 | 3 | ||
| 2 (-1) | 3, -1 | 3 | ||
| 3 (-3) | 3, -1, -3 | 3 | ||
| 4 (5) | 3, it was at index 1 | -3, -1 | 5 | 5 |
| 5 (3) | 5, 3 | 5 | ||
| 6 (6) | 3, 5 | 6 | 6 | |
| 7 (7) | 6 | 7 | 7 |
At end = 4 the window covers indexes 2 to 4. The 3 at index 1 is outside it, so it leaves from the front. Then 5 beats everything that remains.
At end = 3 the queue holds three values in decreasing order. That is the worst case for memory: a run of falling numbers, where every one of them might still become the maximum.
Time O(n). The inner while loop can remove several candidates in one step, but each index is added to the queue once and removed at most once, so the total work across the whole run is about 2n steps. Space O(n) in this version, because the array behind the queue is never trimmed at the front. A true double-ended queue would hold at most k indexes at a time.
Why only one removal from the front
Step 1 uses if, not while. The window moves one place per step, so at most one index falls out of it each time, and the indexes in the queue are in ascending order, so only the front one can be the one that fell out.
The general tool
A queue kept in sorted order like this is often called a monotonic queue. It answers "what is the largest (or smallest) value in a moving range?" in constant time per step. Flipping the comparison in step 2 to >= gives the sliding window minimum. The same structure appears in problems about the shortest subarray reaching a sum when negative numbers are allowed, and in several dynamic programming optimisations.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
const numbers = [1, 3, -1, -3, 5, 3, 6, 7];
console.log(maxSlidingWindow(numbers, 3)); // [3, 3, 5, 5, 6, 7]Python
numbers = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(numbers, 3)) # [3, 3, 5, 5, 6, 7]The comment after each line is the result you should see.
Common mistakes
- Storing values instead of indexes. Without indexes there is no reliable way to tell whether the front has left the window, especially when values repeat.
- Checking the front against the wrong boundary. The window ending at
endstarts atend - k + 1, so an index is out when it is<= end - k. - Reporting before the first window is full. Nothing is output until
endreachesk - 1. - Using
shift()or a sorted list.shift()can cost O(k) each time. Keeping the whole window sorted, or using a heap, costs O(log k) per step and gives O(n log k) overall: acceptable, but not the linear answer. - Removing only smaller values from the back. Using
<instead of<=still gives correct answers, but keeps equal values that the newer one makes redundant.
Original problem: LeetCode 239: Sliding Window Maximum