Sliding Window Maximum
Find the maximum in every window of size k in O(n) using a monotonic deque.
How it works
Sliding Window Maximum finds the largest value in each contiguous subarray of fixed size k across an entire array. A naive approach — rescanning k elements per window — costs O(nk). The key insight is to maintain a monotonic decreasing deque of indices: elements that can never be a future window maximum are discarded eagerly, so each index is added and removed at most once.
The deque stores indices in decreasing order of their array values. When the window slides forward, the front element is evicted if it has fallen outside the window boundary. Before adding a new element, all back elements with values ≤ the new value are popped, because they are dominated and will never be the maximum of any future window.
The result for window ending at index i (once i ≥ k-1) is always arr[deque[0]] — the front of the deque, which holds the index of the current window's maximum.
This O(n) technique generalises to sliding window minimum, range queries, and is the backbone of many stock analysis and stream-processing algorithms.
Complexity
Visualizer
Where it's used in the real world
Stock price rolling maximum
Computing the highest price over a rolling trading windowFinancial analytics dashboards compute rolling N-day highs over millions of ticks. The monotonic deque reduces this from O(nk) to O(n), making real-time dashboards feasible at high-frequency tick resolution without approximation.
Video stream frame analysis
Finding peak brightness or motion intensity in a sliding temporal windowVideo processing pipelines (scene cut detection, HDR tone-mapping) need per-frame statistics over a temporal neighbourhood. The deque-based sliding maximum processes full HD/4K frame sequences at native frame rates in a single pass.
Network traffic burst detection
Identifying peak packet counts in a sliding time window for QoS enforcementNetwork traffic shapers and DDoS mitigation systems enforce per-flow burst limits by tracking the maximum packet rate over a sliding window. The O(n) algorithm lets hardware offload engines evaluate millions of flows per second.
Implementation
function slidingWindowMax(arr: number[], k: number): number[] {
const n = arr.length;
const deque: number[] = []; // stores indices
const result: number[] = [];
for (let i = 0; i < n; i++) {
// Remove indices outside the current window
while (deque.length > 0 && deque[0] <= i - k) deque.shift();
// Maintain decreasing order — pop dominated elements from back
while (deque.length > 0 && arr[deque[deque.length - 1]] <= arr[i]) {
deque.pop();
}
deque.push(i);
// Record max once the first full window is complete
if (i >= k - 1) result.push(arr[deque[0]]);
}
return result;
}
// Usage
console.log(slidingWindowMax([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]