Sliding Window Maximum Using Deque in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sliding Window Maximum for a Simple Array

What is the output of the following C# code that finds the maximum in each sliding window of size 3 using a deque?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        var result = SlidingWindowMax(nums, k);
        Console.WriteLine(string.Join(", ", result));
    }

    static int[] SlidingWindowMax(int[] nums, int k) {
        LinkedList<int> deque = new LinkedList<int>();
        int[] res = new int[nums.Length - k + 1];
        int ri = 0;

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

A [3, 3, 5, 5, 6, 7]

B [1, 3, -1, -3, 5, 3, 6, 7]

C [3, -1, -3, 5, 3, 6]

D [7, 6, 5, 3, -3, -1]

💡 Hint

Focus on how the deque stores indices and removes smaller elements before adding the current index.

The code maintains a deque of indices where the values are in decreasing order. For each window, the front of the deque is the index of the maximum element. The output is the maximum for each sliding window of size 3.

🧠 Conceptual

intermediate

Understanding Deque Operations in Sliding Window Maximum

In the sliding window maximum algorithm using a deque, what is the main reason for removing elements from the back of the deque when the current element is greater than the elements at those indices?

A To keep the deque sorted in increasing order of values

B To maintain the deque in decreasing order of values so the front is always the maximum

C To ensure the deque only contains indices of elements greater than the current element

D To remove indices that are out of the current window range

💡 Hint

Think about how the deque helps find the maximum quickly.

Removing smaller elements from the back keeps the deque in decreasing order of values, so the front always holds the index of the maximum element in the current window.

🔧 Debug

advanced

Identify the Error in Sliding Window Maximum Implementation

What error will the following code produce when run, and why?

DSA C#

int[] nums = {4, 2, 12, 3, 8};
int k = 3;
LinkedList<int> deque = new LinkedList<int>();
int[] res = new int[nums.Length - k + 1];
int ri = 0;

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

A InvalidOperationException because RemoveFirst is called on empty deque

B NullReferenceException because deque is empty at start

C IndexOutOfRangeException because the loop runs one step too far

D No error, code runs correctly

💡 Hint

Check the loop boundary condition carefully.

The loop runs from i = 0 to i = nums.Length inclusive, but nums[nums.Length] is out of range causing IndexOutOfRangeException.

🚀 Application

advanced

Number of Maximum Elements Stored in Deque

Given an array of length n and window size k, what is the maximum number of indices that can be stored in the deque at any time during the sliding window maximum algorithm?

A 1

B n

C k + 1

D k

💡 Hint

Consider the window size and how many indices can be relevant at once.

The deque stores indices only from the current window, so at most k indices can be stored.

❓ Predict Output

expert

Output of Sliding Window Maximum with Negative and Repeated Numbers

What is the output of the following C# code that computes sliding window maximum with window size 4?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] nums = {2, 2, -1, 3, 3, 0, 5, 5};
        int k = 4;
        var result = SlidingWindowMax(nums, k);
        Console.WriteLine(string.Join(", ", result));
    }

    static int[] SlidingWindowMax(int[] nums, int k) {
        LinkedList<int> deque = new LinkedList<int>();
        int[] res = new int[nums.Length - k + 1];
        int ri = 0;

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

A [3, 3, 3, 5, 5]

B [2, 3, 3, 5, 5]

C [3, 3, 0, 5, 5]

D [2, 2, 3, 5, 5]

💡 Hint

Check carefully how repeated maximum values are handled in the deque.

The maximum values for each window of size 4 are 3, 3, 3, 5, and 5 respectively.

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