Sliding Window Maximum Using Deque in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of using a deque in the Sliding Window Maximum problem?

A deque helps keep track of indices of elements in the current window in a way that the front always holds the index of the maximum element. It allows efficient insertion and removal from both ends to maintain the window's maximum.

beginner

In the Sliding Window Maximum problem, why do we remove elements from the back of the deque when a new element arrives?

We remove elements from the back if they are smaller than the new element because they cannot be the maximum if a bigger element is now in the window. This keeps the deque elements in decreasing order.

beginner

What does the deque store in the Sliding Window Maximum algorithm?

The deque stores indices of elements from the array, not the elements themselves. This helps to check if elements are out of the current window and to access their values easily.

intermediate

How do you know when to remove the front element of the deque in the Sliding Window Maximum problem?

If the index at the front of the deque is outside the current window (less than current index minus window size plus 1), it should be removed because it is no longer part of the window.

intermediate

What is the time complexity of the Sliding Window Maximum algorithm using a deque and why?

The time complexity is O(n) because each element is added and removed from the deque at most once, making the operations linear in total.

What does the front of the deque represent in the Sliding Window Maximum algorithm?

A The newest element added to the window

B Index of the minimum element in the current window

C The oldest element in the array

D Index of the maximum element in the current window

The front of the deque always holds the index of the maximum element in the current sliding window.

Why do we remove elements from the back of the deque when a new element is larger?

A Because smaller elements cannot be maximum if a bigger element is present

B To keep the deque sorted in ascending order

C To remove duplicates

D To reduce the size of the deque to one

Removing smaller elements from the back ensures the deque only keeps candidates for maximum in decreasing order.

What happens if the front element of the deque is outside the current window?

A It is removed from the front

B It is moved to the back

C It stays in the deque

D The window size is increased

Elements outside the current window are removed from the front to keep the deque valid for the current window.

What is stored inside the deque in the Sliding Window Maximum algorithm?

A Sum of elements

B Indices of elements

C Window sizes

D Actual element values

The deque stores indices so we can check window boundaries and access element values easily.

What is the overall time complexity of the Sliding Window Maximum algorithm using a deque?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

Each element is pushed and popped at most once, resulting in linear time complexity.

Explain how a deque helps solve the Sliding Window Maximum problem efficiently.

Think about how the deque keeps track of candidates for maximum.

Describe the step-by-step process of updating the deque when moving the sliding window by one position.

Focus on how the deque changes with each new element.

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