Sliding Window Maximum Using Deque in DSA C#

Mental Model

Keep track of useful elements in a window using a double-ended queue so we can quickly find the maximum.

Analogy: Imagine a line of people waiting to enter a ride. The tallest person in the current group is always at the front, and as people leave or new ones join, we update the line to keep the tallest visible easily.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size k=4
Deque stores indices of elements in decreasing order of their values
Example deque state:
Indices: 4 -> 5
Values:  6 -> 3
Window covers indices 2 to 5

Dry Run Walkthrough

Input: array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], window size k=4

Goal: Find the maximum value in every window of size 4 as it slides from left to right

Step 1: Process first element 2, add its index 0 to deque

Deque: [0]
Window: [2] (indices 0 to 0)

Why: Start building deque with first element index

Step 2: Process element 1 at index 1, 1 < 2 so add index 1 to deque end

Deque: [0, 1]
Window: [2, 1] (indices 0 to 1)

Why: Keep indices of elements in decreasing order of values

Step 3: Process element 3 at index 2, remove indices with smaller values (1 and 0 < 3), remove index 1 and 0, add index 2

Deque: [2]
Window: [2, 1, 3] (indices 0 to 2)

Why: Remove smaller elements as 3 is bigger and will be max in window

Step 4: Process element 4 at index 3, remove index 2 (3 < 4), add index 3

Deque: [3]
Window: [2, 1, 3, 4] (indices 0 to 3)

Why: Keep only indices of elements that can be max in current window

Step 5: Window reached size 4, max is element at deque front index 3 (value 4), slide window forward

Max for window [2,1,3,4] is 4
Deque: [3]

Why: Output max for first window

Step 6: Slide window: remove out-of-window indices from front if any (none), process element 6 at index 4, remove index 3 (4 < 6), add index 4

Deque: [4]
Window: [1, 3, 4, 6] (indices 1 to 4)

Why: Maintain deque for new window

Step 7: Max for window [1,3,4,6] is element at index 4 (6), slide window

Max: 6
Deque: [4]

Why: Output max for second window

Step 8: Process element 3 at index 5, 3 < 6, add index 5

Deque: [4, 5]
Window: [3, 4, 6, 3] (indices 2 to 5)

Why: Add smaller element index to deque end

Step 9: Max for window [3,4,6,3] is element at index 4 (6), slide window

Max: 6
Deque: [4, 5]

Why: Output max for third window

Step 10: Slide window: remove out-of-window indices from front if any (none), process element 8 at index 6, remove indices 5 and 4 (3 and 6 < 8), add index 6

Deque: [6]
Window: [4, 6, 3, 8] (indices 3 to 6)

Why: Remove smaller elements, add new bigger element

Step 11: Max for window [4,6,3,8] is element at index 6 (8), slide window

Max: 8
Deque: [6]

Why: Output max for fourth window

Step 12: Process element 9 at index 7, remove index 6 (8 < 9), add index 7

Deque: [7]
Window: [6, 3, 8, 9] (indices 4 to 7)

Why: Keep max element index at front

Step 13: Max for window [6,3,8,9] is element at index 7 (9), slide window

Max: 9
Deque: [7]

Why: Output max for fifth window

Step 14: Process element 10 at index 8, remove index 7 (9 < 10), add index 8

Deque: [8]
Window: [3, 8, 9, 10] (indices 5 to 8)

Why: Update deque with new max candidate

Step 15: Max for window [3,8,9,10] is element at index 8 (10), slide window

Max: 10
Deque: [8]

Why: Output max for sixth window

Step 16: Process element 12 at index 9, remove index 8 (10 < 12), add index 9

Deque: [9]
Window: [8, 9, 10, 12] (indices 6 to 9)

Why: Keep max element index updated

Step 17: Max for window [8,9,10,12] is element at index 9 (12), slide window

Max: 12
Deque: [9]

Why: Output max for seventh window

Step 18: Process element 56 at index 10, remove index 9 (12 < 56), add index 10

Deque: [10]
Window: [9, 10, 12, 56] (indices 7 to 10)

Why: Update deque with new max

Step 19: Max for window [9,10,12,56] is element at index 10 (56)

Max: 56
Deque: [10]

Why: Output max for last window

Result:

Max values for each window: 4 -> 6 -> 6 -> 8 -> 9 -> 10 -> 12 -> 56

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class SlidingWindowMaximum
{
    public static int[] MaxSlidingWindow(int[] nums, int k)
    {
        if (nums == null || nums.Length == 0 || k <= 0) return new int[0];

        int n = nums.Length;
        int[] result = new int[n - k + 1];
        LinkedList<int> deque = new LinkedList<int>(); // stores indices

        for (int i = 0; i < n; i++)
        {
            // Remove indices out of current window
            while (deque.Count > 0 && deque.First.Value <= i - k)
                deque.RemoveFirst();

            // Remove smaller values at the end as they are useless
            while (deque.Count > 0 && nums[deque.Last.Value] < nums[i])
                deque.RemoveLast();

            deque.AddLast(i); // Add current index

            // Start adding max to result when first window is complete
            if (i >= k - 1)
                result[i - k + 1] = nums[deque.First.Value];
        }

        return result;
    }

    static void Main()
    {
        int[] nums = {2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56};
        int k = 4;
        int[] maxValues = MaxSlidingWindow(nums, k);
        Console.WriteLine(string.Join(" -> ", maxValues));
    }
}

while (deque.Count > 0 && deque.First.Value <= i - k) deque.RemoveFirst();

Remove indices that are out of the current sliding window

while (deque.Count > 0 && nums[deque.Last.Value] < nums[i]) deque.RemoveLast();

Remove indices of elements smaller than current element to maintain decreasing order

deque.AddLast(i);

Add current element index to deque

if (i >= k - 1) result[i - k + 1] = nums[deque.First.Value];

Record max for current window from front of deque

Output

4 -> 6 -> 6 -> 8 -> 9 -> 10 -> 12 -> 56

Complexity Analysis

Time: O(n) because each element is added and removed from the deque at most once

Space: O(k) because the deque stores indices only for the current window of size k

vs Alternative: Naive approach is O(n*k) by scanning each window fully; deque approach is much faster with O(n)

Edge Cases

Empty array

Returns empty result array immediately

DSA C#

if (nums == null || nums.Length == 0 || k <= 0) return new int[0];

Window size k is 1

Each element is max of its own window, returns original array

DSA C#

No special guard needed; algorithm naturally handles k=1

Window size k equals array length

Returns single max value of entire array

DSA C#

Algorithm handles this by producing one result after full traversal

When to Use This Pattern

When asked to find maximum or minimum in every sliding window efficiently, use the deque pattern to maintain candidates in order and achieve O(n) time.

Common Mistakes

Mistake: Not removing indices that are out of the current window from the front of the deque
Fix: Add a check to remove deque front indices when they fall outside the window range

Mistake: Not removing smaller elements from the back before adding new element index
Fix: Remove all smaller elements from the deque's end to keep it decreasing

Summary

Finds the maximum value in every sliding window of size k using a deque.

Use when you need fast maximum queries over moving windows in arrays.

Keep indices of elements in a deque in decreasing order and remove outdated or smaller elements as the window slides.

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