Sliding Window Maximum Using Deque in DSA C - Execution Trace

Concept Flow - Sliding Window Maximum Using Deque

Start

↓

Initialize empty deque

↓

For each element in array

↓

Remove indices out of window from front

↓

Remove smaller elements from back

↓

Add current index to back

↓

If window formed, record max from front

↓

Repeat until end

↓

Return max list

↓

End

The deque keeps indexes of useful elements in current window. Front always has max. Remove out-of-window and smaller elements before adding new.

Execution Sample

DSA C

int arr[] = {1,3,-1,-3,5,3,6,7};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
// Sliding window max using deque
for (int i = 0; i < n; i++) {
  // Remove out of window
  // Remove smaller
  // Add current
  // Record max
}

This code finds max in each sliding window of size k using a deque to track useful elements.

Execution Table

Step	Operation	Deque Content (indexes)	Deque Content (values)	Window Max	Visual State
1	Add index 0 (value 1)	[0]	[1]	-	Deque: [1] | Window: [1]
2	Add index 1 (value 3), remove smaller (1)	[1]	[3]	-	Deque: [3] | Window: [1,3]
3	Add index 2 (value -1)	[1,2]	[3,-1]	3	Deque: [3,-1] | Window: [1,3,-1] Max=3
4	Add index 3 (value -3), remove smaller none	[1,2,3]	[3,-1,-3]	3	Deque: [3,-1,-3] | Window: [3,-1,-3] Max=3
5	Add index 4 (value 5), remove smaller (3,-1,-3)	[4]	[5]	5	Deque: [5] | Window: [-1,-3,5] Max=5
6	Add index 5 (value 3), remove smaller none	[4,5]	[5,3]	5	Deque: [5,3] | Window: [-3,5,3] Max=5
7	Add index 6 (value 6), remove smaller (3,5)	[6]	[6]	6	Deque: [6] | Window: [5,3,6] Max=6
8	Add index 7 (value 7), remove smaller (6)	[7]	[7]	7	Deque: [7] | Window: [3,6,7] Max=7
9	End of array, output max list	-	-	-	Max list: [3,3,5,5,6,7]

💡 All elements processed, max for each window recorded.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
Deque (indexes)	[]	[0]	[1]	[1,2]	[1,2,3]	[4]	[4,5]	[6]	[7]	[]
Deque (values)	[]	[1]	[3]	[3,-1]	[3,-1,-3]	[5]	[5,3]	[6]	[7]	[]
Window Max List	[]	[]	[]	[3]	[3,3]	[3,3,5]	[3,3,5,5]	[3,3,5,5,6]	[3,3,5,5,6,7]	[3,3,5,5,6,7]

Key Moments - 3 Insights

Why do we remove smaller elements from the back of the deque before adding a new element?

Because smaller elements cannot be maximum if a bigger element comes later. Removing them keeps deque front as max. See steps 2, 5, 7 in execution_table where smaller elements are removed.

Why do we remove indices from the front of the deque when they are out of the current window?

Because those elements are no longer in the sliding window and can't be max. Removing them keeps deque valid for current window. See step 5 where index 1 is removed as window moves.

Why does the deque store indices instead of values?

Indices help check if elements are out of window and also access values from original array. Values alone can't track window position. This is shown in variable_tracker where deque stores indexes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the content of the deque (indexes)?

A [4]

B [1,2,3,4]

C [2,3,4]

D [3,4]

💡 Hint

Check the 'Deque Content (indexes)' column at Step 5 in execution_table.

At which step does the window first produce a maximum value output?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Window Max' column in execution_table to find first non '-' value.

If we did not remove smaller elements from the back, how would the deque content change at Step 7?

A [1,2,3,6]

B [6]

C [4,5,6]

D [4,5,6,7]

💡 Hint

Refer to Step 7 in execution_table and think what happens if smaller elements are not removed.

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use deque to store indexes of useful elements
- Remove indexes out of window from front
- Remove smaller elements from back before adding new
- Front of deque always max in current window
- Record max after first full window
- 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. The deque stores indexes of elements that might be maximum in the current window. For each new element, we remove indexes that are out of the window from the front and remove smaller elements from the back to keep the deque valid. The front of the deque always holds the index of the maximum element for the current window. We record this maximum once the first full window is formed and continue until the end of the array. The execution table tracks the deque content and window max at each step, while the variable tracker shows how the deque and max list evolve. Key moments address why smaller elements are removed and why indices are stored. The quiz tests understanding of deque content and output timing. This method runs in linear time, making it efficient for large arrays.