Sliding Window Maximum Using Deque in DSA C++ - 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 >= elements at those indices

↓

Add current index to back

↓

Remove front if it is out of current window

↓

If window is formed, record element at front as max

↓

Move to next element

↓

Repeat until end of array

The deque keeps indices of elements in decreasing order. For each new element, remove smaller or equal elements from back, add current index, remove front if out of window, then record max from front.

Execution Sample

DSA C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  deque<int> dq;
  vector<int> result;
  for (int i = 0; i < nums.size(); i++) {
    while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
    dq.push_back(i);
    if (dq.front() <= i - k) dq.pop_front();
    if (i >= k - 1) result.push_back(nums[dq.front()]);
  }
  return result;
}

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

Execution Table

Step	Operation	Current Index i	Deque Indices	Deque Values	Max for Window	Visual State
1	Start	-	[]	[]	-	[]
2	Process element 1	0	[0]	[1]	-	[1]
3	Process element 3, remove 1 (since 3 >= 1)	1	[1]	[3]	-	[3]
4	Process element -1, add index	2	[1,2]	[3,-1]	3	[3,-1]
5	Process element -3, add index	3	[1,2,3]	[3,-1,-3]	3	[3,-1,-3]
6	Process element 5, remove -3,-1,3	4	[4]	[5]	5	[5]
7	Process element 3, add index	5	[4,5]	[5,3]	5	[5,3]
8	Process element 6, remove 3,5	6	[6]	[6]	6	[6]
9	Process element 7, remove 6	7	[7]	[7]	7	[7]
10	Process element 2, add index	8	[7,8]	[7,2]	7	[7,2]
11	End of array	-	[7,8]	[7,2]	7	[7,2]

💡 Reached end of array, all windows processed.

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	8
deque indices	[]	[0]	[1]	[1,2]	[1,2,3]	[4]	[4,5]	[6]	[7]	[7,8]	[7,8]
max values	[]	[]	[]	[3]	[3]	[5]	[5]	[6]	[7]	[7]	[7]

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 this or future windows, so we remove them to keep deque elements in decreasing order (see steps 3 and 6 in execution_table).

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

The front of the deque holds the index of the maximum element for the current window. If it is outside the window (index <= i-k), it must be removed to keep the window valid (see step 10).

Why do we store indices in the deque instead of values?

Indices help us check if elements are out of the current window and also access their values easily. Values alone don't give position info (see variable_tracker and execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the deque indices state?

A [1,2,3]

B [4]

C [1,2,3,4]

D [0,4]

💡 Hint

Check the 'Deque Indices' column at step 6 in execution_table.

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

A Step 4

B Step 2

C Step 5

D Step 3

💡 Hint

Look at the 'Max for Window' column in execution_table to see when the first max appears.

If the window size k was increased, how would the deque indices change at step 10?

A Deque would be empty

B More indices would be removed from front

C Deque would have more indices because window is larger

D Deque indices remain the same

💡 Hint

Consider how window size affects which indices stay in deque as per variable_tracker.

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use deque to store indices of elements in decreasing order
- Remove smaller or equal elements from back before adding new
- Remove front if out of window
- Front of deque is max for current window
- Efficient O(n) solution for max in each window

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 indices of elements in decreasing order of their values. For each new element, smaller or equal elements at the back are removed because they cannot be maximum anymore. The current index is added to the back. If the front index is out of the current window, it is removed. The element at the front of the deque is the maximum for the current window. This process repeats for all elements, producing the maximum for each sliding window efficiently.

Practice

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

easy

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

B. To sort the entire array before processing windows

C. To reverse the array for easier maximum calculation

D. To store the actual maximum values of each window directly

Solution

1. Step 1: Understand the role of deque

   The deque stores indices of elements in the current window, maintaining them in decreasing order of their values.

2. Step 2: How deque helps find maximum

   The front of the deque always holds the index of the maximum element for the current window, allowing O(1) access.

3. Final Answer:

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

4. Quick Check:

   Deque stores indices for max retrieval [OK]

Hint: Deque keeps max candidates' indices for quick max retrieval [OK]

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Assuming deque sorts the entire array
• Believing deque reverses the array

2. Which of the following C++ deque operations is used to remove elements from the back while maintaining the sliding window maximum?

easy

A. push_front()

B. pop_front()

C. pop_back()

D. push_back()

Solution

1. Step 1: Identify deque operation for removing from back

   pop_back() removes the last element from the deque, which is used to discard smaller elements behind the current element.

2. Step 2: Why pop_back() is used here

   We remove elements from the back that are smaller than the current element to maintain decreasing order in the deque.

3. Final Answer:

   pop_back() -> Option C

4. Quick Check:

   pop_back() removes smaller elements from back [OK]

Hint: Use pop_back() to remove smaller elements behind current [OK]

Common Mistakes:

• Using pop_front() instead of pop_back() to remove from back
• Confusing push operations with pop operations
• Removing elements from front incorrectly

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. [2, 3, 4, 6, 8, 9, 10, 12, 56]

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

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

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

Solution

1. Step 1: Slide window and find max for each window

   Windows and max values: [2,1,3,4] -> 4, [1,3,4,6] -> 6, [3,4,6,3] -> 6, [4,6,3,8] -> 8, [6,3,8,9] -> 9, [3,8,9,10] -> 10, [8,9,10,12] -> 12, [9,10,12,56] -> 56

2. Step 2: Collect all max values in order

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

3. Final Answer:

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

4. Quick Check:

   Sliding window max matches [4, 6, 6, 8, 9, 10, 12, 56] [OK]

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

Common Mistakes:

• Confusing window size or missing last windows
• Incorrectly calculating max for each window
• Off-by-one errors in output length

4. Identify the bug in this snippet for sliding window maximum using deque:

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) result.push_back(arr[dq.front()]);
}

medium

A. The condition to pop front should be dq.front() <= i - k - 1

B. The condition to pop front should be dq.front() < i - k

C. The condition to pop front should be dq.front() == i - k + 1

D. The condition to pop front should be dq.front() < i - k + 1

Solution

1. Step 1: Understand when to remove front index

   The front index should be removed if it is out of the current window. The window covers indices [i-k+1, i]. So indices less than i-k+1 are out.

2. Step 2: Correct condition for popping front

   The condition should be dq.front() <= i - k to remove indices outside the window.

3. Final Answer:

   The condition to pop front should be dq.front() <= i - k -> Option B

4. Quick Check:

   Pop front if index outside window [OK]

Hint: Pop front if index <= window start - 1 (i-k) [OK]

Common Mistakes:

• Using equality instead of less than for popping front
• Off-by-one errors in window boundary
• Not removing outdated indices from deque

5. Given an array [1, 3, -1, -3, 5, 3, 6, 7] and window size 3, how would you modify the deque approach to also return the minimum in each sliding window along with the maximum?

hard

A. Use two deques: one for max (decreasing) and one for min (increasing) values

B. Use one deque and store pairs of (max, min) values

C. Sort each window to find max and min

D. Use a priority queue for max and a stack for min

Solution

1. Step 1: Understand separate tracking for max and min

   To get both max and min efficiently, maintain two deques: one keeps indices of max candidates in decreasing order, the other keeps indices of min candidates in increasing order.

2. Step 2: How two deques work together

   For each window, the front of max deque gives max, front of min deque gives min. Both deques are updated similarly but with opposite ordering.

3. Final Answer:

   Use two deques: one for max (decreasing) and one for min (increasing) values -> Option A

4. Quick Check:

   Two deques track max and min separately [OK]

Hint: Maintain two deques: max decreasing, min increasing [OK]

Common Mistakes:

• Trying to store both max and min in one deque
• Sorting each window (inefficient)
• Using wrong data structures for min tracking