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 sliding window maximum algorithm using a deque for the given array and window size?

DSA C++

std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
// Sliding window maximum algorithm using deque
std::deque<int> dq;
std::vector<int> result;
for (int i = 0; i < nums.size(); ++i) {
    while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
    while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
    dq.push_back(i);
    if (i >= k - 1) result.push_back(nums[dq.front()]);
}
for (int val : result) std::cout << val << " ";

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

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

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

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

💡 Hint

Remember the deque stores indices of elements in decreasing order of their values within the current window.

The sliding window maximum for window size 3 moves over the array and picks the maximum in each window. The output is the maximum values for windows: [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7].

🧠 Conceptual

intermediate

Understanding the Role of Deque in Sliding Window Maximum

Why do we use a deque to solve the sliding window maximum problem efficiently?

A Because deque allows insertion and deletion from both ends in O(1) time, helping maintain candidates for maximum efficiently.

B Because deque sorts the elements automatically to find the maximum.

C Because deque stores all elements of the array to find the maximum later.

D Because deque duplicates the array elements to speed up the search.

💡 Hint

Think about how we maintain the maximum candidate elements as the window slides.

Deque helps keep track of indices of elements in decreasing order of their values. It allows removing elements that are out of the current window or smaller than the current element efficiently from both ends.

🔧 Debug

advanced

Identify the Bug in Sliding Window Maximum Code

What error does the following code produce when run for sliding window maximum?

DSA C++

std::vector<int> nums = {4, 2, 12, 3, 8};
int k = 3;
std::deque<int> dq;
std::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 (i >= k - 1) {
        if (dq.front() <= i - k) dq.pop_front();
        result.push_back(nums[dq.front()]);
    }
}
for (int val : result) std::cout << val << " ";

A The code produces a runtime error due to accessing empty deque.

B The output is incorrect because the window boundary check is done after pushing the maximum, causing stale indices.

C The code produces a syntax error due to missing semicolon.

D The output is correct and prints the sliding window maximum.

💡 Hint

Check the order of popping elements outside the window and pushing the maximum.

The code checks and removes indices outside the window after pushing the maximum, so stale indices may be included in the result. The check for removing old indices should happen before pushing the maximum value.

❓ Predict Output

advanced

Output of Sliding Window Maximum for Decreasing Array

What is the output of the sliding window maximum algorithm using a deque for the array [9, 7, 5, 3, 1] with window size 2?

DSA C++

std::vector<int> nums = {9, 7, 5, 3, 1};
int k = 2;
std::deque<int> dq;
std::vector<int> result;
for (int i = 0; i < nums.size(); ++i) {
    while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
    while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
    dq.push_back(i);
    if (i >= k - 1) result.push_back(nums[dq.front()]);
}
for (int val : result) std::cout << val << " ";

A [9, 7, 5, 3]

B [7, 5, 3, 1]

C [9, 9, 9, 9]

D [1, 3, 5, 7]

💡 Hint

The array is strictly decreasing, so the first element in each window is the maximum.

For window size 2, the windows are [9,7], [7,5], [5,3], [3,1]. The maximums are the first elements in each window: 9, 7, 5, 3.

🧠 Conceptual

expert

Time Complexity of Sliding Window Maximum Using Deque

What is the time complexity of the sliding window maximum algorithm using a deque for an array of size n and window size k?

A O(k*log n), because we use a priority queue internally.

B O(n*k), because for each element we check k elements in the window.

C O(n), because each element is pushed and popped at most once from the deque.

D O(n^2), because of nested loops over the array.

💡 Hint

Consider how many times each element can be added or removed from the deque.

Each element is pushed into the deque once and popped at most once, so total operations are proportional to n, making the algorithm O(n).

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