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 front if out of window

↓

Remove indices from back while current element > elements at those indices

↓

Add current index to back

↓

If window formed, record element at front as max

↓

Repeat until end of array

We slide over the array, keeping indices of useful elements in a deque. We remove indices out of the window and smaller elements behind current to keep max at front.

Execution Sample

DSA C#

using System.Collections.Generic;
int[] nums = {1,3,-1,-3,5,3,6,7};
int k = 3;
LinkedList<int> dq = new LinkedList<int>();
int[] result = new int[nums.Length - k + 1];
for (int i = 0; i < nums.Length; i++) {
  // Remove out of window from front
  while (dq.Count > 0 && dq.First.Value <= i - k) {
    dq.RemoveFirst();
  }
  // Remove smaller from back
  while (dq.Count > 0 && nums[dq.Last.Value] < nums[i]) {
    dq.RemoveLast();
  }
  // Add current
  dq.AddLast(i);
  // Record max if window full
  if (i >= k - 1) {
    result[i - k + 1] = nums[dq.First.Value];
  }
}

This code slides a window of size k over nums, using a deque to track max elements efficiently.

Execution Table

Step	Operation	Deque Indices	Deque Values	Window Max	Visual State
1	Add index 0 (value 1)	[0]	[1]	N/A	Deque: 1
2	Add index 1 (value 3), remove 0 since 3 > 1	[1]	[3]	N/A	Deque: 3
3	Add index 2 (value -1)	[1,2]	[3,-1]	3	Window [1,3,-1], Max=3
4	Remove index 1 if out of window? No Add index 3 (value -3), remove none	[1,2,3]	[3,-1,-3]	3	Window [3,-1,-3], Max=3
5	Remove index 1 if out of window? Yes (i=4, window start=2) Remove indices 2,3 since 5 > -1 and -3 Add index 4 (value 5)	[4]	[5]	5	Window [-1,-3,5], Max=5
6	Remove index 4 if out of window? No Remove index 4 if 3 > 5? No Add index 5 (value 3)	[4,5]	[5,3]	5	Window [-3,5,3], Max=5
7	Remove index 4 if out of window? No Remove indices 5 since 6 > 3 Remove index 4 since 6 > 5 Add index 6 (value 6)	[6]	[6]	6	Window [5,3,6], Max=6
8	Remove index 6 if out of window? No Remove index 6 since 7 > 6 Add index 7 (value 7)	[7]	[7]	7	Window [3,6,7], Max=7
9	End of array reached	[7]	[7]	7	Final max recorded

💡 Reached end of array, all windows processed

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
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]
Window Max	N/A	N/A	3	3	5	5	6	7	7	7

Key Moments - 3 Insights

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

Because smaller elements behind current can't be max in future windows. See execution_table rows 2, 5, and 7 where removals happen to keep max at front.

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

Indices at front represent elements no longer in the window. Removing them keeps the deque valid for current window max. See execution_table row 5 where index 1 is removed as window moves.

Why is the max element always at the front of the deque?

Because we remove smaller elements behind current, the largest element's index stays at front. This is shown in execution_table where max is always deque front value.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, which indices are removed from the deque before adding index 4?

A Indices 0 and 1

B Indices 2 and 3

C Indices 1 and 2

D No indices removed

💡 Hint

Check the 'Operation' and 'Deque Indices' columns at Step 5 in execution_table

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

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'Window Max' column in execution_table to find first non-N/A value

If the window size k was 2 instead of 3, how would the deque indices change at Step 5?

A Index 4 would be added without removals

B Index 0 would be removed earlier

C Index 1 would not be removed from front

D Indices 2 and 3 would remain

💡 Hint

Consider when indices are removed from front based on window size, check Step 5 removal logic

Concept Snapshot

Sliding Window Maximum Using Deque:
- Use deque to store indices of useful elements
- Remove indices out of window from front
- Remove smaller elements from back before adding current
- Max is always at front of deque
- Slide window over array, record max at each step

Full Transcript

This concept shows how to find the maximum in every sliding window of size k in an array using a deque. We keep indices of elements in the deque. For each new element, we remove indices from the front if they are out of the current window. We also remove indices from the back if their values are smaller than the current element, ensuring the largest element's index is always at the front. We add the current index to the back. When the window is fully formed, the element at the front of the deque is the maximum for that window. This process repeats until the end of the array.

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

B. To sort the entire array before processing

C. To reverse the array elements

D. To store the sum of elements in the window

Solution

1. Step 1: Understand the role of deque in sliding window

   The 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 -> Option A

4. Quick Check:

   Deque stores max indices = To store indices of elements in a way that helps find the maximum in O(1) time [OK]

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

Common Mistakes:

• Thinking deque stores actual values instead of indices
• Assuming deque sorts the entire array
• Confusing deque with a stack or queue only

2. Which of the following C# code snippets correctly initializes a deque to be used for sliding window maximum?

easy

A. var deque = new Stack<int>();

B. var deque = new LinkedList<int>();

C. var deque = new Queue<int>();

D. var deque = new List<int>();

Solution

1. Step 1: Identify the correct data structure for deque in C#

   C# does not have a built-in deque class, but LinkedList<T> supports adding/removing from both ends, acting as a deque.

2. Step 2: Why LinkedList is suitable

   LinkedList allows efficient insertion and removal from front and back, which is essential for deque operations in sliding window maximum.

3. Final Answer:

   var deque = new LinkedList<int>(); -> Option B

4. Quick Check:

   LinkedList supports deque operations = var deque = new LinkedList<int>(); [OK]

Hint: Use LinkedList for deque in C# since no built-in deque [OK]

Common Mistakes:

• Using Queue which only supports FIFO
• Using Stack which only supports LIFO
• Using List which is inefficient for front removals

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

medium

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

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

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

D. [3, 4, 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: Write the max values as output array

   The output array is [4, 6, 6, 8, 9, 10, 12, 56].

3. Final Answer:

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

4. Quick Check:

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

Hint: Check max in each window carefully, watch overlapping elements [OK]

Common Mistakes:

• Confusing max with last element in window
• Missing last window max
• Off-by-one errors in window sliding

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

for (int i = 0; i < nums.Length; i++) {
  while (deque.Count > 0 && nums[deque.Last.Value] <= nums[i]) {
    deque.RemoveLast();
  }
  deque.AddLast(i);
  if (deque.First.Value >= i - k) {
    deque.RemoveFirst();
  }
  if (i >= k - 1) {
    result.Add(nums[deque.First.Value]);
  }
}

medium

A. The deque should store values, not indices

B. The condition to remove from front should be < instead of <=

C. The condition to remove from back should be >= instead of <=

D. The condition to remove from front should be <= instead of >=

Solution

1. Step 1: Analyze condition for removing front index

   The condition 'deque.First.Value >= i - k' removes indices inside the window since valid front indices are >= i - k + 1 which is always true for >= i - k, causing incorrect removal of current max candidates.

2. Step 2: Correct condition to remove outdated indices

   Window covers [i-k+1 to i], remove if deque.First.Value < i - k + 1 i.e. deque.First.Value <= i - k.

3. Final Answer:

   The condition to remove from front should be <= instead of >= -> Option D

4. Quick Check:

   Remove outdated indices with <= i - k condition [OK]

Hint: Check window boundary condition carefully for removing front index [OK]

Common Mistakes:

• Using >= instead of <= causes removing valid indices
• Removing from back incorrectly
• Storing values instead of indices in deque

5. Given an array nums = [1,3,-1,-3,5,3,6,7] and window size k = 3, how would you modify the sliding window maximum algorithm using deque to also return the indices of the maximum elements for each window?

hard

A. Store values in deque and output their positions from the array

B. Store indices in deque and output nums[deque.Last.Value] for each window

C. Store indices in deque and output deque.First.Value for each window

D. Store values in deque and output the maximum value only

Solution

1. Step 1: Understand what deque stores

   The deque stores indices of elements, not values, to track positions and efficiently remove outdated indices.

2. Step 2: Output indices of maximum elements

   The maximum element's index is always at the front of the deque, so outputting deque.First.Value for each window gives the index of the max element.

3. Final Answer:

   Store indices in deque and output deque.First.Value for each window -> Option C

4. Quick Check:

   Deque front index = max element index [OK]

Hint: Deque front holds max index; output it per window [OK]

Common Mistakes:

• Storing values instead of indices in deque
• Outputting deque.Last.Value instead of First
• Confusing values with indices in output