Sliding Window Maximum
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 recomputing the max from scratch for every window position is too slow. When the window slides right by one, we add one new element on the right and remove one old element on the left. The challenge is tracking the maximum efficiently as elements enter and leave.
We don't need to keep every element in the window, only the ones that could still become the maximum. If a newer element is larger than an older one, the older element can never be the maximum for any window that contains the newer one. Discarding those elements leads to a monotonic deque, which is the optimal solution below.
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 (output equals input) or equal to n (one window, the global max).
Approach 1: Brute Force
Intuition
For each window position, scan all k elements and find the maximum. There are n - k + 1 windows, and each window has k elements, so we loop through every window and compute its max directly.
This mirrors what the problem asks for and needs no extra data structures, which makes it a good correctness baseline before optimizing.
Algorithm
- Create a result array of size
n - k + 1. - For each starting index
ifrom 0 ton - k: - Find the maximum of
nums[i]throughnums[i + k - 1]. - 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 carry over from the previous window. The next approach reuses that work by keeping the elements in a data structure that tracks the maximum as elements enter and leave.
Approach 2: Max-Heap (Priority Queue)
Intuition
A max-heap gives the maximum in O(1) and supports insertion in O(log n). The difficulty is removal: when the window slides right, the leftmost element leaves, but deleting an arbitrary element from a binary heap is not a cheap operation.
The workaround is lazy deletion. We store pairs of (value, index) in the heap and never delete an element when it leaves the window. When we peek at the top, we check whether its index is still inside the current window. If it is not, we pop it and check the next one. Stale elements are removed only once they reach the top, so we never pay to delete an element buried in the middle of the heap.
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:
- Add the new element to the heap as (value, index).
- While the top element's index is outside the current window (index <= i - k), pop it.
- The heap's top is the maximum for this window. Add it to the result.
- Return the result.
Example Walkthrough
The heap stores (value, index) pairs ordered by value. The top is the candidate maximum; we discard it only if its index has left the window. Tracing nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:
In this trace no stale element ever sits at the top, so no lazy deletion fires. Lazy deletion matters on inputs like a descending prefix followed by larger values, where an out-of-window element can surface at the top and must be popped before reading the max.
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 an ordering over all elements in the window, but we only ever read the maximum. The next approach keeps only the candidates for the maximum in a structure with O(1) amortized operations, which removes the log factor entirely.
Approach 3: Monotonic Deque (Optimal)
Intuition
Consider which elements in the window can still 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 of any window that contains both. The reason: nums[j] is at least as large and stays in the window longer, since it entered later and so it also leaves later. Once a larger or equal element appears to its right, nums[i] is dominated and can be discarded.
This leads to a deque (double-ended queue) holding indices whose values are in decreasing order from front to back. The front holds the index of the current window's maximum. When a new element enters, we remove every element from the back whose value is smaller or equal, add the new element, and drop the front if it has slid out of the window.
The back-removal loop can pop several elements in a single iteration, so a single step is not O(1) in the worst case. The bound holds when amortized over the whole array: each index is added to the deque exactly once and removed at most once, either from the back when a larger or equal element arrives, or from the front when it slides out of the window. The total number of deque operations across all n iterations is therefore at most 2n, which averages to O(1) per element.
Algorithm
- Create an empty deque (stores indices) and a result array.
- For each index
ifrom 0 to n-1: - Remove indices from the front of the deque if they are outside the window (index <= i - k).
- Remove indices from the back of the deque while the element at those indices is less than or equal to
nums[i]. - Add index
ito the back of the deque. - If
i >= k - 1(we have filled the first window), the front of the deque is the max for this window. Addnums[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.