How do you find the maximum in every sliding window of size k?
Keep a deque of indices whose values are in decreasing order. Drop indices that left the window from the front, drop smaller values from the back before adding the new index, and the front is always the window maximum.
Explain it simply
Think of a batting line-up where you only care about the strongest batter among the last k overs. If a new batter is stronger than someone already waiting, the weaker one will never be the best again, because the new batter stays in the window longer. So remove the weaker ones.
The deque keeps candidates in decreasing strength. The front is the current best. When the front slips out of the window, discard it.
Example
function maxSlidingWindow(nums, k) {
const dq = []; // indices, values decreasing
const result = [];
for (let i = 0; i < nums.length; i++) {
if (dq.length && dq[0] <= i - k) dq.shift(); // out of window
while (dq.length && nums[dq[dq.length - 1]] < nums[i]) dq.pop();
dq.push(i);
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)); // Output: [3,3,5,5,6,7]Complexity
Time O(n), space O(k).
What to say in the interview
"Recomputing the max for each window is O(n k). I use a monotonic deque of indices: remove expired indices from the front, remove smaller values from the back, then read the front. Each index enters and leaves once, so it is O(n). In JavaScript, shift on a plain array is O(n), so a real deque or head pointer keeps it truly linear."
Common mistakes
- Storing values instead of indices, so expired items cannot be detected.
- Forgetting to start recording results only once the first full window exists (i >= k - 1).