Sliding Window Maximum
Last Updated: March 29, 2026
Understanding the Problem
We have an array and a window of fixed size k that slides from left to right, one element at a time. For each position of the window, we need to report the maximum element inside it.
The array has up to 100,000 elements, so we need something smarter than recomputing the max from scratch for every window position. The core challenge is this: when the window slides right by one, we add one new element on the right and remove one old element on the left. How do we efficiently track the maximum as elements enter and leave?
The key observation is that we don't need to keep every element in the window, just the ones that could potentially be the maximum. If a newer element is larger than an older one, the older element can never be the maximum for any future window. This "discard the useless" idea leads us to a monotonic deque.
Key Constraints:
1 <= nums.length <= 10^5-- We need O(n) or O(n log n). An O(n * k) brute force could hit 10^10 operations in the worst case (k close to n), which is too slow.-10^4 <= nums[i] <= 10^4-- Values can be negative. The max of a window could be negative.1 <= k <= nums.length-- k can be 1 (trivial, output equals input) or equal to n (single window, just find the global max).
Approach 1: Brute Force
Intuition
The simplest approach: for each window position, scan all k elements and find the maximum. We have n - k + 1 windows, and each window has k elements, so we just loop through every window and compute its max directly.
This is straightforward and easy to get right. It mirrors exactly what the problem asks us to do, no clever data structures needed.
Algorithm
- Create a result array of size
n - k + 1. - For each starting index
ifrom 0 ton - k:
a. Find the maximum of nums[i] through nums[i + k - 1].
b. Store it in result[i].
- Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n * k). We have n - k + 1 windows, and for each we scan k elements. In the worst case when k is close to n, this becomes O(n^2).
- Space Complexity: O(1). Beyond the output array, we only use a couple of variables.
For each window, we rescan all k elements even though k-1 of them are the same as the previous window. What if we used a data structure that efficiently tracks the maximum as elements enter and leave?
Approach 2: Max-Heap (Priority Queue)
Intuition
Since we need the maximum of each window, a max-heap seems like a natural fit. A heap can give us the max in O(1) and lets us insert in O(log n). The trick is handling removals: when the window slides right, the leftmost element leaves the window, but removing an arbitrary element from a heap is expensive.
Here is the clever workaround: don't remove elements eagerly. Instead, use "lazy deletion." We store pairs of (value, index) in the heap. When we peek at the top, we check if its index is still within the current window. If not, we pop it and check the next one. Elements that have left the window eventually get cleaned up when they bubble to the top.
Algorithm
- Create a max-heap (priority queue) and a result array.
- Add the first k elements to the heap as (value, index) pairs.
- The heap's top is the maximum for the first window. Add it to the result.
- For each new element from index k to n-1:
a. Add the new element to the heap as (value, index).
b. While the top element's index is outside the current window (index <= i - k), pop it.
c. The heap's top is the maximum for this window. Add it to the result.
- Return the result.
Code
- Time Complexity: O(n log n). Each element is pushed onto the heap once (O(log n) per push) and popped at most once (O(log n) per pop). Over n elements, that is O(n log n) total.
- Space Complexity: O(n). In the worst case, the heap holds all n elements if the array is sorted in ascending order.
The heap maintains a full ordering of elements, but we only need the maximum. What if we tracked just the candidates for the maximum in a structure that supports O(1) amortized operations?
Approach 3: Monotonic Deque (Optimal)
Intuition
Here is the key insight that makes this problem elegant. Think about what elements in the window actually matter. If there is an element at index i and a later element at index j > i where nums[j] >= nums[i], then nums[i] can never be the maximum for any window that contains both. Why? Because nums[j] is at least as large and will stay in the window longer (it entered later, so it leaves later). So nums[i] is useless, and we can discard it.
This observation leads us to maintain a deque (double-ended queue) where the elements are in strictly decreasing order from front to back. The front always holds the index of the current window's maximum. When a new element enters, we remove all elements from the back that are smaller, add the new element, and check if the front has fallen out of the window.
The monotonic deque works because it exploits a simple truth: if a newer element is larger than an older one, the older one is permanently irrelevant. By evicting smaller elements from the back before adding a new one, we guarantee the deque is always sorted in decreasing order. The front is always the maximum.
Each element enters the deque exactly once and leaves at most once (either popped from the back when a larger element arrives, or popped from the front when it slides out of the window). So across all n elements, the total number of deque operations is at most 2n, giving us O(n) amortized time.
Algorithm
- Create an empty deque (stores indices) and a result array.
- For each index
ifrom 0 to n-1:
a. Remove indices from the front of the deque if they are outside the window (index <= i - k).
b. Remove indices from the back of the deque while the element at those indices is less than or equal to nums[i].
c. Add index i to the back of the deque.
d. If i >= k - 1 (we have filled the first window), the front of the deque is the max for this window. Add nums[deque.front] to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n). Each element is added to the deque once and removed at most once. The total number of operations across all iterations is at most 2n, so the amortized cost per element is O(1).
- Space Complexity: O(k). The deque holds at most k indices at any time, since we remove elements that fall outside the window.