Sliding Window Maximum Using Deque in DSA Python - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start with empty deque

↓

For each element in array

↓

Remove indices from back if current element is greater

↓

Add current index to back

↓

Remove front if out of window

↓

Record front element as max for current window

↓

Move to next element

↓

Repeat until end of array

We keep indexes of useful elements in a deque, removing smaller elements from the back and removing elements out of the window from the front, so the front always holds the max.

Execution Sample

DSA Python

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i in range(len(nums)):
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

This code finds the maximum in each sliding window of size k using a deque to track indices of max candidates.

Execution Table

Step	Operation	Current Index (i)	Deque Content (indices)	Deque Values	Action	Max Recorded
1	Start	-	[]	[]	Initialize empty deque	-
2	Process element	0	[0]	[1]	Add index 0	-
3	Process element	1	[1]	[3]	Pop 0 (1 < 3), add 1	-
4	Process element	2	[1,2]	[3, -1]	Add 2 (no pop)	-
5	Process element	3	[3]	[6]	Pop 2 (-1 < 6), pop 1 (3 < 6), add 3	6
6	Process element	4	[3,4]	[6, 4]	Add 4 (no pop)	6
7	Process element	5	[3,5]	[6, 5]	Pop 4 (4 < 5), add 5	6
8	Process element	6	[6]	[7]	Pop 5 (5 < 7), pop 3 (6 < 7), add 6	7
9	Process element	7	[7]	[8]	Pop 6 (7 < 8), add 7	8
10	Process element	8	[8]	[9]	Pop 7 (8 < 9), add 8	9
11	End	-	[8]	[9]	Finished processing all elements	9

💡 All elements processed, max for each window recorded.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
i	-	0	1	2	3	4	5	6	7	8	-
deque (indices)	[]	[0]	[1]	[1,2]	[3]	[3,4]	[3,5]	[6]	[7]	[8]	[8]
max recorded	[]	[]	[]	[]	[6]	[6,6]	[6,6,6]	[6,6,6,7]	[6,6,6,7,8]	[6,6,6,7,8,9]	[6,6,6,7,8,9]

Key Moments - 3 Insights

Why do we remove elements from the back of the deque when the current element is greater?

Because smaller elements behind the current one cannot be maximum in the current or future windows, so we remove them to keep only useful candidates (see steps 3, 5, 8 in execution_table).

Why do we remove the front element if it is out of the current window?

The front holds the index of the maximum element for the current window. If it is out of the window (older than i - k), it must be removed to keep the window valid (as per the code condition if dq[0] <= i - k).

Why do we record the max only when i >= k - 1?

Because before that, the window is not full size yet, so we don't have a complete window maximum to record (see steps 2-4 where max is not recorded).

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the content of the deque after processing element at index 3?

A [2, 3]

B [1, 2, 3]

C [3]

D [0, 3]

💡 Hint

Check the 'Deque Content (indices)' column at step 5 in execution_table.

At which step does the first maximum get recorded in the max recorded list?

A Step 2

B Step 5

C Step 4

D Step 3

💡 Hint

Look at the 'Max Recorded' column in execution_table to see when the first value appears.

If the window size k was 2 instead of 3, how would the max recording step change?

A Max would be recorded starting at i=1

B Max would be recorded starting at i=2

C Max would be recorded starting at i=0

D Max would be recorded starting at i=3

💡 Hint

Recall max is recorded when i >= k - 1; check variable_tracker for i values.

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use deque to store indices of elements
- Remove smaller elements from back before adding new
- Remove front if out of window
- Front always max of current window
- Record max when window size reached
- Efficient O(n) solution for max in sliding windows

Full Transcript

This visualization shows how to find the maximum in each sliding window of size k in an array using a deque. We keep indices of useful elements in the deque. For each new element, we remove smaller elements from the back because they cannot be maximum anymore. We add the current index to the back. If the front index is out of the current window, we remove it. The front of the deque always holds the index of the maximum element for the current window. We record the maximum once the window is fully formed. The execution table traces each step, showing how the deque changes and when maximums are recorded. Key moments clarify why we remove elements and when we record maximums. The quiz tests understanding of deque content and max recording timing. This method runs efficiently in linear time.