Algorithm

Sliding Window Max

Monotonic Stack Pattern

Sliding Window Maximum

You are given an array of integers nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the maximum of the sliding window. Return an array of the maximums for each window position.

CONSTRAINTS
  • 1 <= nums.length <= 10⁵
  • -10⁴ <= nums[i] <= 10⁴
  • 1 <= k <= nums.length
EXAMPLE 1
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Windows: [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7.
EXAMPLE 2
Input: nums = [1], k = 1
Output: [1]
Single element array with window size 1. The only window is [1], and its maximum is 1.
EXAMPLE 3
Input: nums = [9,7,5,3,1], k = 3
Output: [9,7,5]
Strictly decreasing array. Each window maximum is its leftmost (largest) element.

Finding the maximum of a moving window is a common challenge in data streaming. As the window slides from left to right, we want to know the largest value currently visible. A naive approach would be to re-scan all k elements of the window every time it moves, but this repeats a massive amount of work, leading to O(N * k) time complexity.

python
# Brute Force (O(N * k) Time, O(1) Space)
res = []
for i in range(len(nums) - k + 1):
    window_max = float('-inf')
    for j in range(i, i + k):
        window_max = max(window_max, nums[j])
    res.append(window_max)
return res

To optimize, we could use a Max-Heap to store the current window's elements. A heap gives us the maximum in O(1) time, but when the window slides, removing the element that fell out takes O(k). We can improve this to O(log N) using a Lazy Removal strategy, where we only remove elements from the top of the heap if they have actually expired from the window.

python
# Max-Heap with Lazy Removal (O(N log N) Time, O(N) Space)
import heapq
heap = [] # Stores (-val, index)
res = []
for i in range(len(nums)):
    heapq.heappush(heap, (-nums[i], i))
    if i >= k - 1:
        # Remove expired elements from the top
        while heap[0][1] <= i - k:
            heapq.heappop(heap)
        res.append(-heap[0][0])
return res

The optimal solution uses a Monotonic Deque (Double-Ended Queue) to achieve true linear time. The core insight is the Redundancy Rule: in a window of size k, an older element becomes useless the moment a later element appears that is larger or equal to it. This is because the newcomer is larger and will stay in the window longer. By discarding these redundant elements, we maintain a buffer of indices where the values are strictly decreasing.

The strategy works as follows:
- Prune from Back: Before adding a new index, we remove all indices from the back of the deque whose values are less than the current value. These are now redundant.
- Expire from Front: We check the index at the front. If it has fallen out of the current window (index <= current_index - k), we remove it.
- The Maximum: After these steps, the index at the very front of the deque is guaranteed to be the maximum for the current window.

python
# Monotonic Deque (O(N) Time, O(k) Space)
from collections import deque
dq = deque() # Stores indices
res = []
for i in range(len(nums)):
    # 1. Prune redundant elements from the back
    while dq and nums[i] >= nums[dq[-1]]:
        dq.pop()
    
    # 2. Add current element
    dq.append(i)
    
    # 3. Expire the front if out of window
    if dq[0] <= i - k:
        dq.popleft()
    
    # 4. Capture result once window is full
    if i >= k - 1:
        res.append(nums[dq[0]])
return res

Because every element enters and leaves the deque exactly once, the entire process takes O(N) time. The deque's ability to push and pop from both ends is what makes this O(1) maintenance possible.

Worked Example:[1, 3, -1, -3, 5, 3, 6, 7], k=3
0
1
i
1
3
2
-1
3
-3
4
5
5
3
6
6
7
7
Process i = 0 (val 1): Push index 0 onto Deque. Deque indices = [0] (values: [1]). Window size (1) < k (3), no output yet.
0
1
1
3
i
2
-1
3
-3
4
5
5
3
6
6
7
7
Process i = 1 (val 3): 3 >= 1. Prune index 0 from back of Deque (value 1 is dominated). Push index 1. Deque indices = [1] (values: [3]). Window size (2) < k (3), no output.
0
1
1
3
Max (3)
2
-1
i
3
-3
4
5
5
3
6
6
7
7
Process i = 2 (val -1): -1 < 3. No pruning, push index 2. Deque indices = [1, 2] (values: [3, -1]). Window size (3) >= k. Front of Deque is index 1 (val 3). Record Max = 3.
0
1
1
3
Max (3)
2
-1
3
-3
i
4
5
5
3
6
6
7
7
Process i = 3 (val -3): -3 < -1. Push index 3. Deque indices = [1, 2, 3] (values: [3, -1, -3]). Front of Deque is index 1 (val 3). Record Max = 3.
0
1
1
3
2
-1
3
-3
4
5
iMax (5)
5
3
6
6
7
7
Process i = 4 (val 5): 5 >= -3 and 5 >= -1. Prune indices 3 and 2 from back. Front index 1 (val 3) has expired (1 < 4-3+1). Remove 1. Push index 4. Deque indices = [4] (value: [5]). Record Max = 5.
0
1
1
3
2
-1
3
-3
4
5
Max (5)
5
3
i
6
6
7
7
Process i = 5 (val 3): 3 < 5. Push index 5. Deque indices = [4, 5] (values: [5, 3]). Front is index 4 (val 5). Record Max = 5.
0
1
1
3
2
-1
3
-3
4
5
5
3
6
6
iMax (6)
7
7
Process i = 6 (val 6): 6 >= 3 and 6 >= 5. Prune indices 5 and 4 from back. Push index 6. Deque indices = [6] (value: [6]). Record Max = 6.
0
1
1
3
2
-1
3
-3
4
5
5
3
6
6
7
7
iMax (7)
Process i = 7 (val 7): 7 >= 6. Prune index 6 from back. Push index 7. Deque indices = [7] (value: [7]). Record Max = 7. Final output: [3, 3, 5, 5, 6, 7].
Interactive Strategy Visualization
MONOTONIC QUEUE INSIGHT

Sliding Window Maximum Mechanics

1
3
-1
-3
5
3
6
7
MONOTONIC DEQUE
Empty

Mental Model

  • Descending Deque: Stores values in descending order. The front is always the max.
  • Obsolescence: If a new value is larger than existing ones, the smaller ones can never be max again.
LOGICSTEP 1/9
Process [1, 3, -1, -3, 5, 3, 6, 7], k=3
TIP

Amortized O(N)

Each index is pushed and popped at most ONCE. Thus, the total complexity is O(N)!

O(N * k) Brute Force
→
O(N log N) Max-Heap
→
O(N) Monotonic Deque