Sliding Window Maximum: definition
Find the largest value in each consecutive window of a fixed size as it moves through an array.
Task example: Sliding Window Maximum
Given an integer array nums and a window size k, return the maximum of every contiguous group of k elements, from left to right. Move the window one position each time. Do not change nums.
The array is nonempty, and 1 ≤ k ≤ len(nums). Negative numbers and duplicates are allowed. There are n - k + 1 answers.
Brute force: video explanation
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]
Prefer reading? Follow the steps below.
- Try each starting index from 0 through n - k. Initialize largest from the first value of that window, not zero.
- Compare the other k - 1 values with largest. Keep the larger value after each comparison.
- Append largest to the answer. Move the window one position and scan it again. For the example, the maxima are [3, 3, 5, 5, 6, 7].
Time complexity · O(nk)
Each of n - k + 1 windows checks k values. The exact bound is O((n - k + 1)k), often simplified to O(nk).
Space complexity · O(1) auxiliary
Only indices and the current maximum are needed besides the returned list. The output itself stores n - k + 1 values.
Monotonic deque: video explanation
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]
Prefer reading? Follow the steps below.
- Keep indices in a deque, a queue with fast removal at both ends. Values decrease from front to back, so the front is the maximum candidate.
- Remove an expired index from the front. Remove smaller or equal values from the back before adding the incoming index: the new value is at least as large and expires later.
- After k values have arrived, append nums[q[0]]. Repeat for each incoming value. Store indices, not just values, so expiration is unambiguous.
The deque reuses useful candidates instead of rescanning overlapping windows. Keeping the newer of equal values is safe because it remains in the window longer.
Time complexity · O(n)
Each index is appended once and removed at most once. All deque operations together take O(n), even though there is a nested while loop.
Space complexity · O(k) auxiliary
The deque holds at most k indices, reached for a decreasing window. The returned list separately stores n - k + 1 values.