Sliding Window Maximum Using Deque in DSA C++ - Build from Scratch

Sliding Window Maximum Using Deque

📖 Scenario: You are working on a real-time data monitoring system that tracks temperature readings every minute. To analyze recent trends, you want to find the maximum temperature in the last k minutes efficiently.

🎯 Goal: Build a C++ program that uses a deque to find the maximum value in every sliding window of size k over a list of temperature readings.

📋 What You'll Learn

Create a vector called temperatures with the exact values: {4, 3, 5, 4, 3, 3, 6, 7}

Create an integer variable called k and set it to 3

Use a deque<int> called dq to store indices of elements

Implement the sliding window maximum logic using the deque

Print the maximum values for each sliding window separated by spaces

💡 Why This Matters

🌍 Real World

Sliding window maximum is used in real-time data analysis, such as monitoring temperature, stock prices, or network traffic to quickly find recent maximum values.

💼 Career

Understanding sliding window techniques and deque usage is important for software engineers working on performance-critical applications and real-time data processing.

1

Create the temperature readings vector

Create a std::vector<int> called temperatures with these exact values: {4, 3, 5, 4, 3, 3, 6, 7}

DSA C++

#include 
#include 
#include 

int main() {
    // Create the temperatures vector
    // Your code here

    return 0;
}

Hint

Use std::vector<int> temperatures = {4, 3, 5, 4, 3, 3, 6, 7}; to create the vector.

2

Set the sliding window size

Create an integer variable called k and set it to 3

DSA C++

#include 
#include 
#include 

int main() {
    std::vector temperatures = {4, 3, 5, 4, 3, 3, 6, 7};
    // Set the window size k
    // Your code here

    return 0;
}

Hint

Write int k = 3; to set the window size.

3

Implement sliding window maximum logic using deque

Use a std::deque<int> called dq to store indices. Write a for loop with variable i from 0 to temperatures.size(). Inside the loop, remove indices from the back of dq while the current temperature is greater than or equal to the temperature at those indices. Remove indices from the front if they are out of the current window. Add i to the back of dq. After the first k - 1 iterations, store the temperature at the front index of dq as the maximum for the current window in a vector called max_temps.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector temperatures = {4, 3, 5, 4, 3, 3, 6, 7};
    int k = 3;

    // Implement sliding window maximum using deque
    // Your code here

    return 0;
}

Hint

Use a deque to keep indices of useful elements. Remove smaller elements from the back and remove elements out of the window from the front. Add the front element's temperature to max_temps after the first window.

4

Print the maximum temperatures for each sliding window

Use a for loop with variable val to iterate over max_temps and print each value followed by a space using std::cout. Then print a newline.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector temperatures = {4, 3, 5, 4, 3, 3, 6, 7};
    int k = 3;

    std::deque dq;
    std::vector max_temps;

    for (int i = 0; i = temperatures[dq.back()]) {
            dq.pop_back();
        }
        if (!dq.empty() && dq.front() = k - 1) {
            max_temps.push_back(temperatures[dq.front()]);
        }
    }

    // Print the max_temps vector
    // Your code here

    return 0;
}

Hint

Use a range-based for loop to print each value in max_temps followed by a space, then print a newline.

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