Why is the naive sliding window maximum approach inefficient?

Scanning each window independently to find its maximum takes O(k) time per window, and with n-k+1 windows total, that gives O(n·k) overall — quadratic-like behavior when k is a significant fraction of n.

Why does the deque store indices instead of values?

Storing indices lets the algorithm efficiently check whether the front element has fallen outside the current window (by comparing its index to the window's left boundary), which wouldn't be possible if only values were stored.

Why is the optimal solution's time complexity O(n) instead of O(n log k)?

Although a heap-based solution can achieve O(n log k), the monotonic deque approach is more efficient because each array index is added to and removed from the deque at most once across the whole algorithm, giving true linear O(n) total work.

Can the same technique solve sliding window minimum?

Yes. Sliding window minimum uses the identical monotonic deque technique, just maintaining an increasing order of values instead of decreasing, so the front of the deque holds the current window's minimum instead of its maximum.

What data structure alternatives exist besides a monotonic deque?

A max-heap (priority queue) with lazy deletion of expired indices is a common alternative, achieving O(n log k) time — slightly worse than the deque's O(n) but sometimes simpler to reason about.

Computer Science

Sliding Window Maximum

A technique and classic problem for finding the maximum value in every fixed-size window of an array

IntermediateTechnique6.5K learners

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…

#SlidingWindowMaximum #ComputerScience#Technique#Intermediate#AmortizedTimeComplexity #LongestCommonSubsequence #SpaceComplexity #SoftwareEngineering#Glossary#SkillVeris

Definition

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

Computing rolling maximum for time-series or streaming data analysis

Real-time monitoring systems tracking peak values over a moving time window

Solving sliding window minimum with the same monotonic deque technique

Signal processing tasks requiring windowed extremum tracking

A staple coding interview question testing deque and amortized analysis understanding

Optimizing image processing operations like max pooling over sliding windows

Frequently Asked Questions

From the Blog

Programming

SQL Tutorial for Beginners: With Real Examples

SQL is the language of data — used by data analysts, backend developers, and data scientists every day. This tutorial covers SELECT, WHERE, ORDER BY, GROUP BY, HAVING, JOINs, subqueries, and window functions with real examples you can run immediately.