Sliding Window Maximum Using Deque in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a deque of integers.

DSA C++

std::deque<int> [1];

Drag options to blanks, or click blank then click option'

Alist

Bdq

Cqueue

Dstack

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'queue' or 'stack' which are different container types.

Using 'list' which is a linked list, not a deque.

The deque is declared as std::deque dq; which creates a double-ended queue named dq.

2fill in blank

medium

Complete the code to remove elements from the back of the deque while the current element is greater.

DSA C++

while (!dq.empty() && nums[dq.back()] [1] nums[i]) {
    dq.pop_back();
}

Drag options to blanks, or click blank then click option'

A<=

B>

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' which reverses the logic.

Using '==' which does not remove smaller elements.

We remove elements from the back while nums[dq.back()] < nums[i] to maintain decreasing order in the deque.

3fill in blank

hard

Fix the error in the condition to remove elements out of the current window from the front of the deque.

DSA C++

if (!dq.empty() && dq.front() [1]= i - k) {
    dq.pop_front();
}

Drag options to blanks, or click blank then click option'

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' alone misses elements exactly at the boundary.

Using '>' or '>=' reverses the logic.

We remove elements from the front if dq.front() <= i - k, meaning they are out of the current window.

4fill in blank

hard

Fill both blanks to correctly assign the maximum value of the current window to the result vector.

DSA C++

if (i >= [1] - 1) {
    result.push_back(nums[[2].front()]);
}

Drag options to blanks, or click blank then click option'

Ak

Bdq

Cwindow

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'window' which is undefined.

Using 'i' instead of 'k' for the window size check.

We start adding max values to result when i >= k - 1, and the max is at nums[dq.front()].

5fill in blank

hard

Fill all three blanks to complete the sliding window maximum function using deque.

DSA C++

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

Drag options to blanks, or click blank then click option'

Adq

Bqueue

Cdeq

Dwindow

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for the deque causing errors.

Using undefined variable names like 'window' or 'queue'.

The deque variable is named 'dq' consistently throughout the function to store indices of elements.

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