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.

Practice

1. What is the main purpose of using a deque in the Sliding Window Maximum problem?

easy

A. To store the sum of elements in each window

B. To sort the array elements before processing

C. To reverse the array for easier traversal

D. To store indices of elements in a way that helps find the maximum in O(1) time per window

Solution

1. Step 1: Understand the role of deque

   A deque stores indices of elements in a way that the front always has the index of the maximum element for the current window.

2. Step 2: Why deque helps in O(1) max retrieval

   Because the deque maintains elements in decreasing order, the maximum is always at the front, allowing quick access without scanning the window.

3. Final Answer:

   To store indices of elements in a way that helps find the maximum in O(1) time per window -> Option D

4. Quick Check:

   Deque stores max indices for O(1) max retrieval [OK]

Hint: Deque keeps max at front for quick max retrieval [OK]

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Using deque to sort elements
• Using deque to store sums

2. Which of the following is the correct way to declare a deque in C for storing integer indices?

easy

A. struct deque dq; // assuming a deque struct is defined

B. deque<int> dq;

C. int dq[];

D. deque dq = new deque();

Solution

1. Step 1: Understand C data structure declaration

   C does not have built-in deque type; we use structs or arrays to implement it.

2. Step 2: Identify correct syntax

   struct deque dq; // assuming a deque struct is defined shows a struct declaration which is the correct way in C if a deque struct is defined.

3. Final Answer:

   struct deque dq; // assuming a deque struct is defined -> Option A

4. Quick Check:

   C uses structs for custom data types [OK]

Hint: Use struct for deque in C, no built-in deque type [OK]

Common Mistakes:

• Using C++ syntax like deque<int>
• Trying to declare deque like an array without size
• Using Java or other language syntax

3. What is the output of the sliding window maximum for array [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56] with window size 4?

medium

A. [3, 4, 6, 6, 8, 9, 10, 12, 56]

B. [2, 3, 4, 6, 8, 9, 10, 12]

C. [4, 6, 6, 8, 9, 10, 12, 56]

D. [6, 6, 8, 9, 10, 12, 56]

Solution

1. Step 1: Slide window and find max for each window of size 4

   Windows and max values:
   Window 1: [2,1,3,4] max=4
   Window 2: [1,3,4,6] max=6
   Window 3: [3,4,6,3] max=6
   Window 4: [4,6,3,8] max=8
   Window 5: [6,3,8,9] max=9
   Window 6: [3,8,9,10] max=10
   Window 7: [8,9,10,12] max=12
   Window 8: [9,10,12,56] max=56

2. Step 2: Collect all max values in order

   The max values are [4, 6, 6, 8, 9, 10, 12, 56]

3. Final Answer:

   [4, 6, 6, 8, 9, 10, 12, 56] -> Option C

4. Quick Check:

   Max per window = [4,6,6,8,9,10,12,56] [OK]

Hint: Slide window, track max with deque front [OK]

Common Mistakes:

• Including partial windows smaller than size 4
• Off-by-one errors in window indexing
• Confusing max values with sums

4. Given this snippet for sliding window maximum, what is the bug?

for (int i = 0; i < n; i++) {
  while (!dq.empty() && arr[dq.back()] <= arr[i])
    dq.pop_back();
  dq.push_back(i);
  if (dq.front() <= i - k)
    dq.pop_front();
  if (i >= k - 1)
    printf("%d ", arr[dq.front()]);
}

medium

A. The condition to pop front should be < instead of <=

B. No bug, code is correct

C. The condition to pop front should be checked before pushing current index

D. The order of popping from back and pushing is wrong

Solution

1. Step 1: Analyze deque maintenance logic

   The code pops smaller elements from back before pushing current index, ensuring decreasing order.

2. Step 2: Check window boundary condition

   The code pops front if the front index is out of current window (<= i-k), which is correct.

3. Step 3: Confirm output printing

   Printing starts after first full window (i >= k-1), printing max at front index.

4. Final Answer:

   No bug, code is correct -> Option B

5. Quick Check:

   Deque logic and conditions are correct [OK]

Hint: Check deque front removal after pushing current index [OK]

Common Mistakes:

• Removing front before pushing current index
• Using wrong comparison operators in conditions
• Printing output before full window

5. How would you modify the sliding window maximum algorithm using deque to find the sliding window minimum instead?

hard

A. Change the comparison from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] when popping from back

B. Reverse the array before applying the same algorithm

C. Use a stack instead of a deque

D. Change the window size to half

Solution

1. Step 1: Understand max vs min logic in deque

   For max, we pop from back while elements are smaller or equal. For min, we pop while elements are greater or equal.

2. Step 2: Modify comparison operator

   Change condition from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] to maintain increasing order for min.

3. Final Answer:

   Change the comparison from arr[dq.back()] <= arr[i] to arr[dq.back()] >= arr[i] when popping from back -> Option A

4. Quick Check:

   Reverse comparison for min sliding window [OK]

Hint: Flip comparison sign to find min instead of max [OK]

Common Mistakes:

• Reversing array instead of changing comparison
• Using stack which doesn't maintain order
• Changing window size unnecessarily