DATA STRUCTURES • ALGORITHMS

Sliding Window Maximum

Finding the maximum element in each contiguous window of size K as it moves from the start to the end of an array.

Time

O(N)

Space

O(K)

Key Principle 1

Monotonic Queue (Deque) strategy

Key Principle 2

Remove indices out of window range

Key Principle 3

Maintain elements in decreasing order

Key Principle 4

Front of Deque is always the max

SW_MAX_LAB
ARRAY:
K:
Current Step
Sliding window of size k=3. Track max using monotonic deque.
Playback
Deque & Result ⠿
DEQUE (Indices)
RESULT
Monotonic Logic ⠿
1deque<int> dq;
2for (int i = 0; i < n; i++) {
3    if (!dq.empty() && dq.front() == i - k) dq.pop_front();
4    while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
5    dq.push_back(i);
6    if (i >= k - 1) res.push_back(nums[dq.front()]);
7}
1
[0]
3
[1]
-1
[2]
-3
[3]
5
[4]
3
[5]
6
[6]
7
[7]

Loading Lab...