Sliding Window Maximum

Definition

Sliding Window Maximum refers to both a classic algorithmic problem — finding the maximum element in every contiguous window of fixed size k as it slides across an array — and the deque-based technique commonly used to solve it in linear time.

Overview

The naive approach to finding the maximum of every k-sized window in an array of length n is to scan each window independently, giving O(n·k) time, since every window requires its own linear scan to find its maximum. This becomes impractical when both n and k are large, and the problem is a common way to teach how a well-chosen data structure can turn a quadratic-feeling problem into a linear one. The standard efficient solution uses a double-ended queue (deque) that stores indices, not values, and maintains a critical invariant: the values at the indices in the deque are always in decreasing order from front to back. As the window slides one position to the right, two things happen. First, any indices at the back of the deque whose values are smaller than the new element being added are popped off, since they can never be the maximum of any future window once a larger, more recent element has appeared — a small but important insight, since a later, larger element makes earlier, smaller elements permanently irrelevant. Second, if the index at the front of the deque has fallen outside the current window, it's popped from the front. After both steps, the front of the deque always holds the index of the current window's maximum. Because each array index is pushed onto and popped off the deque at most once across the entire algorithm, the total work is O(n) despite each individual window lookup being effectively O(1) amortized. This monotonic deque pattern generalizes well beyond this specific problem — it's the same core idea behind solving sliding window minimum, and appears in other problems that require efficiently tracking an extremum over a moving range, such as certain formulations of the largest rectangle in a histogram problem. It's a frequently asked technical interview question precisely because the naive solution is obvious but the optimal deque-based solution requires a genuine insight rather than a memorized pattern.

Key Concepts

• Classic problem: maximum of every contiguous window of size k as it slides across an array
• Naive per-window scan approach runs in O(n·k) time
• Optimal solution uses a monotonic decreasing deque of indices
• Deque invariant: values at stored indices are always decreasing front to back
• Elements smaller than a newly added element are evicted, since they can never be a future maximum
• Expired indices outside the current window are popped from the front
• Achieves O(n) total time since each index is pushed/popped at most once
• Same monotonic deque pattern generalizes to sliding window minimum

Use Cases

Frequently Asked Questions

Related in Computer Science