Difficulty: 🔴 Hard
Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue

Solution

LeetCode 239 - Sliding Window Maximum

Problem Understanding

The problem gives us an integer array nums and a window size k. A sliding window of length k starts at the beginning of the array and moves one position to the right at a time. For every position of this window, we must determine the maximum value inside that window.

For example, if the window size is 3, then the first window covers indices [0, 1, 2], the next window covers [1, 2, 3], and so on until the window reaches the end of the array.

The output should contain one maximum value for every valid window position. Since there are n - k + 1 windows in an array of length n, the result array will also have length n - k + 1.

The constraints are very important here:

nums.length can be as large as 10^5
k can also be as large as 10^5

These limits immediately tell us that an inefficient solution will not pass. A solution that repeatedly scans each window would take too much time.

A naive implementation would examine all k elements for every window. Since there are roughly n windows, that approach would require O(n * k) time. In the worst case, this becomes O(10^10), which is far too slow.

Several edge cases are important:

k = 1, every element is its own window, so the answer is simply the original array.
k = len(nums), there is only one window covering the entire array.
Arrays containing duplicate values.
Arrays containing negative numbers.
Strictly increasing or strictly decreasing arrays, which can stress inefficient data structure operations.

The problem guarantees that k is always valid and that the array is non-empty.

Approaches

Brute Force Approach

The simplest approach is to evaluate every sliding window independently.

For each window position:

Extract the k elements in the current window.
Find the maximum among them.
Append that maximum to the result.

This works because every window is explicitly examined, so the computed maximum is always correct.

However, the performance is poor. There are n - k + 1 windows, and each window requires scanning up to k elements. This leads to O(n * k) time complexity.

With the given constraints, this approach becomes too slow.

Optimal Approach, Monotonic Deque

The key insight is that we do not need to recompute the maximum from scratch every time the window moves.

When the window shifts by one position:

One element leaves the window.
One new element enters the window.

Instead of storing all elements equally, we maintain only the elements that could potentially become the maximum in the future.

A monotonic deque solves this efficiently.

The deque stores indices in decreasing order of their corresponding values. This means:

The front of the deque always contains the index of the maximum element for the current window.
Smaller elements behind a larger incoming element are removed because they can never become maximum later.

This allows every element to be added and removed at most once, producing a linear time solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(1) excluding output	Recomputes maximum for every window
Optimal	O(n)	O(k)	Uses a monotonic deque to maintain candidates for maximum

Algorithm Walkthrough

Optimal Monotonic Deque Algorithm

Create an empty deque that will store indices, not values.

We store indices because we need to know when an element falls outside the current window. 2. Iterate through the array using index i.

At each step, we process the current element nums[i]. 3. Remove indices from the front of the deque if they are outside the current window.

The current window starts at i - k + 1. Any index smaller than this is no longer valid and must be discarded. 4. Remove indices from the back of the deque while their corresponding values are smaller than the current value.

If nums[i] is larger than those values, those smaller elements can never become the maximum in any future window that includes nums[i]. 5. Add the current index to the back of the deque.

The deque remains in decreasing order of values. 6. Once the first complete window is formed, meaning i >= k - 1, record the maximum.

The maximum is always at the front of the deque because the deque maintains decreasing order. 7. Continue until all elements are processed.

Why it works

The deque always maintains indices in decreasing order of their values. The front of the deque is therefore always the largest element in the current window.

Any smaller element behind a larger incoming element is removed because it can never become useful again. Also, indices outside the current window are discarded immediately.

Since every index enters and leaves the deque at most once, the algorithm remains efficient while always preserving the correct maximum.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = deque()
        result = []

        for i in range(len(nums)):
            # Remove indices outside the current window
            while window and window[0] <= i - k:
                window.popleft()

            # Maintain decreasing order in deque
            while window and nums[window[-1]] < nums[i]:
                window.pop()

            # Add current index
            window.append(i)

            # Record maximum once window is complete
            if i >= k - 1:
                result.append(nums[window[0]])

        return result

The implementation uses Python's collections.deque because it supports efficient insertion and removal from both ends.

The deque stores indices instead of values. This is important because we must determine whether an element is still inside the sliding window.

The first while loop removes outdated indices that are no longer part of the current window.

The second while loop maintains the monotonic decreasing property. Any smaller value behind the current element becomes useless because the current element will dominate future windows.

After inserting the current index, the front of the deque always contains the maximum value for the current window.

Once the first full window is formed, the algorithm appends the maximum to the result array.

Go Solution

func maxSlidingWindow(nums []int, k int) []int {
    deque := []int{}
    result := []int{}

    for i := 0; i < len(nums); i++ {
        // Remove indices outside the current window
        if len(deque) > 0 && deque[0] <= i-k {
            deque = deque[1:]
        }

        // Maintain decreasing order
        for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
            deque = deque[:len(deque)-1]
        }

        // Add current index
        deque = append(deque, i)

        // Record maximum once window is complete
        if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }

    return result
}

The Go implementation follows the same logic as the Python version. Since Go does not have a built-in deque structure, a slice is used to simulate one.

Indices are stored instead of values for the same reason as in Python, window boundary management.

Go slices make it straightforward to remove elements from the front or back using slice operations.

Integer overflow is not a concern because the problem constraints are well within Go's integer range.

Worked Examples

Example 1

Input:

nums = [1,3,-1,-3,5,3,6,7]
k = 3

The deque stores indices, but the table also shows corresponding values for clarity.

i	nums[i]	Action	Deque Indices	Deque Values	Window Max
0	1	Add 0	[0]	[1]	-
1	3	Remove 1, add 1	[1]	[3]	-
2	-1	Add 2	[1,2]	[3,-1]	3
3	-3	Add 3	[1,2,3]	[3,-1,-3]	3
4	5	Remove smaller values, add 4	[4]	[5]	5
5	3	Add 5	[4,5]	[5,3]	5
6	6	Remove smaller values, add 6	[6]	[6]	6
7	7	Remove smaller values, add 7	[7]	[7]	7

Final output:

[3,3,5,5,6,7]

Example 2

Input:

nums = [1]
k = 1

i	nums[i]	Action	Deque	Window Max
0	1	Add 0	[0]	1

Final output:

[1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every element is added and removed from the deque at most once
Space	O(k)	The deque stores at most `k` indices

The important observation is that although there are nested while loops, each index can only enter and leave the deque once. This means the total number of deque operations across the entire algorithm is linear.

The deque never stores more than k elements because it only contains indices from the current window.

Test Cases

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = deque()
        result = []

        for i in range(len(nums)):
            while window and window[0] <= i - k:
                window.popleft()

            while window and nums[window[-1]] < nums[i]:
                window.pop()

            window.append(i)

            if i >= k - 1:
                result.append(nums[window[0]])

        return result

sol = Solution()

assert sol.maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]  # standard example
assert sol.maxSlidingWindow([1], 1) == [1]  # single element array
assert sol.maxSlidingWindow([1,2,3,4,5], 2) == [2,3,4,5]  # increasing sequence
assert sol.maxSlidingWindow([5,4,3,2,1], 2) == [5,4,3,2]  # decreasing sequence
assert sol.maxSlidingWindow([7,7,7,7], 2) == [7,7,7]  # duplicate values
assert sol.maxSlidingWindow([-1,-3,-5,-2], 2) == [-1,-3,-2]  # negative numbers
assert sol.maxSlidingWindow([9,11], 2) == [11]  # window equals array length
assert sol.maxSlidingWindow([4,2,12,3,-1,6], 1) == [4,2,12,3,-1,6]  # k equals 1
assert sol.maxSlidingWindow([1,3,1,2,0,5], 3) == [3,3,2,5]  # mixed values
assert sol.maxSlidingWindow([10,9,8,7,6,5], 3) == [10,9,8,7]  # larger decreasing window

Test	Why
`[1,3,-1,-3,5,3,6,7], k=3`	Validates the standard example
`[1], k=1`	Tests smallest valid input
Increasing sequence	Ensures deque removes smaller elements correctly
Decreasing sequence	Ensures old maximums stay valid
Duplicate values	Verifies handling of equal elements
Negative numbers	Confirms algorithm works with negatives
Window equals array length	Tests single-window scenario
`k=1`	Every element should become its own maximum
Mixed values	Tests frequent deque updates
Larger decreasing window	Stresses window expiration logic

Edge Cases

Window Size Equals One

When k = 1, every window contains exactly one element. A buggy implementation might still perform unnecessary deque operations or mishandle window boundaries.

This implementation handles the case naturally. Every element becomes the maximum of its own window, so the output matches the input array exactly.

Strictly Decreasing Array

In a decreasing sequence such as [5,4,3,2,1], the deque keeps growing because no incoming value removes previous ones.

This case is important because it tests whether the algorithm correctly removes expired indices from the front of the deque. The implementation does this using:

while window and window[0] <= i - k:
    window.popleft()

Without this logic, outdated maximums would remain incorrectly.

Duplicate Values

Arrays with repeated values can expose subtle bugs in monotonic queue implementations.

For example, [7,7,7,7] with k=2 should produce [7,7,7].

The implementation only removes strictly smaller values:

while window and nums[window[-1]] < nums[i]:

Equal values remain in the deque, which preserves correct ordering and window expiration behavior.

Window Covers Entire Array

When k = len(nums), there is only one valid window.

The implementation still works correctly because the algorithm processes all elements and records exactly one maximum when the first full window is completed.

This validates that the logic does not assume multiple windows exist.