Sliding Window Maximum: LeetCode 239 Solution Explained

Sliding Window Maximum (#239) is the Hard problem that sits at the intersection of two patterns you probably already know — fixed-size sliding window and monotonic data structures. Separately, each pattern is manageable. Together, they require you to think about what information to keep and what to discard as the window moves.

This problem is a staple at Google, Amazon, and Microsoft. It appears on nearly every "must-do Hard problems" list because it tests whether you can combine two well-known techniques into a single efficient solution. If you can solve this cleanly, you have demonstrated real pattern fluency.

The task itself is straightforward: given an array of integers and a window of size K, return the maximum value in every position of the window as it slides from left to right. The naive approach is obvious. The optimal approach is where the real learning happens.

You are given an integer array nums and an integer k. There is a sliding window of size k that moves from the very left of the array to the very right. You can only see the k numbers in the window. Each time the window moves one position to the right, you need to return the maximum element inside it.

For example, given nums = [1,3,-1,-3,5,3,6,7] and k = 3, the first window is [1,3,-1] with max 3. The window slides to [3,-1,-3] with max 3, then [-1,-3,5] with max 5, and so on. The output is [3,3,5,5,6,7].

The output array has length n - k + 1, where n is the length of the input. Every element in the output corresponds to one window position. The challenge is computing each window maximum without redundantly scanning the entire window every time.

The most direct approach is to iterate over every window position and find the maximum by scanning all k elements. This gives you an O(n * k) solution. For each of the n - k + 1 windows, you do k comparisons to find the max.

When k is small relative to n, this is acceptable. But when k approaches n — imagine k = 100,000 on an array of length 100,000 — you are doing nearly n squared work. Interview constraints for this problem typically have n up to 100,000, making O(n * k) too slow.

The brute force is still worth writing out in an interview. It shows you understand the problem, gives you a correct baseline to test against, and sets up the conversation about optimization. But you need to move past it.

The key insight is to maintain a double-ended queue (deque) that stores indices of elements in decreasing order of their values. The front of the deque always holds the index of the current window maximum. As the window slides, you perform two maintenance operations: remove from the back any indices whose values are less than or equal to the new element, and remove from the front any index that has fallen outside the window.

Here is the algorithm step by step. For each index i, first remove indices from the front of the deque if they are out of the window (index less than i - k + 1). Then remove indices from the back while the value at those indices is less than or equal to nums[i]. Push i onto the back. Once i >= k - 1, the front of the deque is your answer for this window.

This runs in O(n) time because each index is pushed onto the deque exactly once and popped at most once. The deque never holds more than k elements, so space is O(k) plus the output array.

The deque maintains a decreasing order of candidate values. The element at the front is always the largest in the current window. When a new element enters the window, any element in the deque that is smaller than the new element can never be the window maximum again — the new element is both larger and more recent, so it will outlast the smaller elements in every future window.

This is why you pop from the back: you are removing candidates that are now permanently dominated. They entered the window before the new element and are smaller, so in every future window that contains both, the new element wins. There is no scenario where those smaller elements become the maximum again.

Popping from the front handles the opposite case: the front element might be the largest, but if its index is outside the current window, it is no longer a valid candidate. By storing indices rather than values, you can check this in O(1) — just compare the front index against the left boundary of the window.

The combination of these two operations ensures the deque always contains exactly the indices that could potentially be the maximum of some current or future window, in decreasing order of their values.

When k equals 1, the output is identical to the input — every element is the maximum of its own single-element window. When k equals n, the output is a single element: the global maximum of the entire array. Both cases should work without special handling if your algorithm is correct.

The all-increasing case (e.g., [1,2,3,4,5] with k=3) means every new element dominates, so the deque is always size 1 after processing. The all-decreasing case (e.g., [5,4,3,2,1] with k=3) is trickier: the deque fills up to size k because no element gets popped from the back. Only front pops occur as elements leave the window.

The all-same-values case (e.g., [3,3,3,3] with k=2) tests your comparison operator. If you use strict less-than when popping from the back, equal elements accumulate in the deque unnecessarily. Using less-than-or-equal keeps the deque lean and still correct.

Sliding window maximum is the canonical problem for the monotonic deque pattern. Once you internalize the technique of maintaining a decreasing deque of indices, you can apply the same idea to sliding window minimum (just reverse the comparison), the stock span problem, and any scenario where you need the extremum of a moving range.

The deeper lesson is about data structure selection. A heap also gives you the maximum, but removing arbitrary elements from a heap is O(k). A balanced BST works but adds complexity. The deque is the right tool because the operations you need — push back, pop back, pop front, peek front — are all O(1).

If you are preparing for coding interviews, make this problem one of your anchor problems for the monotonic deque category. Practice it until you can write the solution from memory, then use YeetCode flashcards to keep the pattern fresh through spaced repetition. The sliding window maximum pattern appears in enough variations that fluency here pays dividends across multiple problems.