Sliding Window Maximum Using Deque in DSA C++ - Deep Dive

Overview - Sliding Window Maximum Using Deque

What is it?

Sliding Window Maximum Using Deque is a technique to find the maximum value in every contiguous subarray (window) of a fixed size within a larger array. It uses a double-ended queue (deque) to efficiently keep track of potential maximums as the window moves. This method avoids recalculating the maximum from scratch for each window, making it much faster than naive approaches. It is especially useful when dealing with large data streams or arrays.

Why it matters

Without this technique, finding the maximum in every window would require checking all elements in each window repeatedly, leading to slow performance. This would make real-time data processing, like monitoring sensor data or stock prices, inefficient or impossible. Sliding Window Maximum Using Deque solves this by updating the maximum quickly as the window slides, enabling fast and scalable solutions.

Where it fits

Before learning this, you should understand arrays, basic loops, and the concept of a queue. After mastering this, you can explore other sliding window problems, advanced data structures like segment trees, and optimization techniques for streaming data.

Mental Model

Core Idea

Keep only the useful elements in a deque so the front always holds the maximum for the current window.

Think of it like...

Imagine a line of people waiting to enter a concert, but only the tallest people stay visible because shorter ones behind them can't be seen. As the line moves forward, people leave and new ones join, but you always see the tallest person at the front.

Array:  [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size: 4

Deque stores indices of elements:

Initial window (indices 0 to 3):
Deque: [3] (value 4 is max)

Slide window by 1:
Deque: [4] (value 6 is max)

Slide window by 1:
Deque: [4, 5] (values 6, 3; max is 6 at front)

Slide window by 1:
Deque: [6] (value 8 is max)

Slide window by 1:
Deque: [7] (value 9 is max)

Slide window by 1:
Deque: [8] (value 10 is max)

Slide window by 1:
Deque: [9] (value 12 is max)

Slide window by 1:
Deque: [10] (value 56 is max)

Each step removes indices out of window and smaller values behind new element.

Build-Up - 7 Steps

1

Foundation

Understanding the Sliding Window Concept

Concept: Learn what a sliding window is and how it moves over an array.

A sliding window is a fixed-size section of an array that moves one step at a time from the start to the end. For example, with an array [1, 3, 5, 2, 8] and window size 3, the windows are [1,3,5], then [3,5,2], then [5,2,8]. We want to find the maximum in each window.

Result

Windows: [1,3,5], [3,5,2], [5,2,8] Maximums: 5, 5, 8

Understanding the sliding window helps you see why recalculating maximums from scratch is inefficient and sets the stage for optimization.

2

Foundation

Basics of Double-Ended Queue (Deque)

Concept: Learn what a deque is and how it allows adding/removing elements from both ends.

A deque is like a line where you can add or remove people from the front or the back. This flexibility helps us keep track of candidates for the maximum efficiently. Operations include push_front, push_back, pop_front, and pop_back.

Result

Deque supports fast insertions and deletions at both ends.

Knowing deque operations is essential because the sliding window maximum algorithm relies on adding and removing elements from both ends quickly.

3

Intermediate

Naive Approach and Its Limitations

🤔Before reading on: do you think checking every element in each window is efficient for large arrays? Commit to yes or no.

Concept: Understand the simple method of finding maximum by scanning each window fully and why it is slow.

For each window, scan all elements inside it to find the maximum. For an array of size n and window size k, this takes O(k) time per window, leading to O(n*k) total time.

Result

For array size 10^5 and window size 10^3, this approach is too slow for real-time use.

Recognizing the inefficiency of the naive approach motivates the need for a better method like using a deque.

4

Intermediate

Maintaining Maximums Using Deque

🤔Before reading on: do you think the deque should store values or indices to track maximums efficiently? Commit to your answer.

Concept: Learn how to store indices in the deque to keep track of potential maximums and remove irrelevant elements.

We store indices of elements in the deque. When a new element arrives, remove indices from the back whose values are less than the new element because they can't be maximum anymore. Remove indices from the front if they are out of the current window. The front of the deque always holds the index of the maximum element.

Result

Deque always contains indices of elements in decreasing order of their values within the current window.

Using indices instead of values allows efficient window boundary checks and keeps the maximum at the front.

5

Intermediate

Step-by-Step Sliding Window Maximum Algorithm

🤔Before reading on: do you think the maximum changes only when the current max leaves the window? Commit to yes or no.

Concept: Combine deque operations to implement the sliding window maximum algorithm efficiently.

1. Initialize an empty deque. 2. Process the first k elements: remove smaller elements from back, add current index. 3. For each element from k to end: - The front of deque is max for previous window. - Remove indices out of current window from front. - Remove smaller elements from back. - Add current index. 4. After processing all, output max for last window.

Result

Maximums for each window are found in O(n) time.

Understanding the stepwise process clarifies how the deque maintains maximums dynamically as the window slides.

6

Advanced

C++ Implementation Using STL Deque

🤔Before reading on: do you think the STL deque supports all needed operations efficiently? Commit to yes or no.

Concept: Learn how to implement the sliding window maximum algorithm in C++ using the standard deque container.

#include #include #include std::vector slidingWindowMax(const std::vector& nums, int k) { std::deque dq; // stores indices std::vector max_values; for (int i = 0; i < nums.size(); ++i) { // Remove indices out of window if (!dq.empty() && dq.front() == i - k) { dq.pop_front(); } // Remove smaller elements from back while (!dq.empty() && nums[dq.back()] < nums[i]) { dq.pop_back(); } dq.push_back(i); // Start adding max values after first window if (i >= k - 1) { max_values.push_back(nums[dq.front()]); } } return max_values; } int main() { std::vector arr = {2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56}; int k = 4; std::vector result = slidingWindowMax(arr, k); for (int val : result) { std::cout << val << " "; } std::cout << std::endl; return 0; }

Result

Output: 4 6 6 8 9 10 12 56

Seeing the full code connects theory to practice and shows how STL deque simplifies implementation.

7

Expert

Performance and Edge Case Analysis

🤔Before reading on: do you think the algorithm always runs in O(n) time regardless of input? Commit to yes or no.

Concept: Understand why the algorithm is O(n), how it handles edge cases, and what can affect performance.

Each element is pushed and popped at most once from the deque, so total operations are O(n). Edge cases include: - Window size k = 1 (max is each element itself) - Window size k equals array size (max is max of entire array) - All elements equal (deque keeps only one index) - Strictly increasing or decreasing sequences Handling these correctly ensures robustness.

Result

Algorithm runs efficiently and correctly for all valid inputs.

Knowing the operation count and edge cases prevents misuse and helps optimize or debug in production.

Under the Hood

The deque stores indices of array elements in decreasing order of their values. When a new element arrives, smaller elements at the back are removed because they cannot be maximum if a bigger element is behind them. The front of the deque always holds the index of the maximum element for the current window. As the window slides, indices that fall out of the window range are removed from the front. This ensures constant time access to the maximum for each window.

Why designed this way?

This design avoids recomputing maximums by maintaining a structure that only keeps candidates for maximum, discarding irrelevant elements early. Alternatives like segment trees or heaps are more complex or slower for this problem. The deque approach balances simplicity and efficiency, making it ideal for real-time or streaming data.

Sliding Window Maximum Mechanism:

Array indices:  0   1   2   3   4   5   6
Values:        [2,  1,  3,  4,  6,  3,  8]

Window size k=3

Step 1: i=0
Deque: [0] (value 2)

Step 2: i=1
Remove smaller from back: 1 < 2? No
Deque: [0,1]

Step 3: i=2
Remove smaller from back: 3 > 1 pop 1, 3 > 2 pop 0
Deque: [2]

Window max at front: index 2 (value 3)

Step 4: i=3
Remove smaller from back: 4 > 3 pop 2
Deque: [3]

Remove out of window: indices < i-k+1 = 1, none
Window max: index 3 (value 4)

... and so on.

Myth Busters - 3 Common Misconceptions

Quick: Does the deque store the actual values or their indices? Commit to your answer.

Common Belief: The deque stores the actual values of the elements to find the maximum.

Reality: The deque stores indices of elements, not the values themselves, to efficiently check window boundaries and maintain order.

Why it matters: Storing values instead of indices makes it impossible to know if an element is outside the current window, leading to incorrect maximums.

Quick: Is the algorithm's time complexity O(n*k) or O(n)? Commit to your answer.

Common Belief: The algorithm takes O(n*k) time because it processes each window separately.

Reality: The algorithm runs in O(n) time because each element is added and removed from the deque at most once.

Why it matters: Misunderstanding the time complexity can lead to rejecting this efficient method for large datasets.

Quick: Does the maximum always change only when the current max leaves the window? Commit to yes or no.

Common Belief: The maximum changes only when the current maximum element leaves the window.

Reality: The maximum can change earlier if a new element larger than the current maximum enters the window, causing smaller elements to be removed.

Why it matters: Assuming maximum changes only on exit leads to incorrect logic and bugs in implementation.

Expert Zone

1

The deque maintains a strictly decreasing sequence of values by removing smaller elements from the back, ensuring the front is always the maximum.

2

When multiple elements have the same value, their indices are kept in order to maintain correct window boundaries and maximum selection.

3

The algorithm's O(n) time complexity relies on each element being pushed and popped at most once, a subtle point often overlooked.

When NOT to use

This approach is not suitable when you need to find minimums or other statistics simultaneously; specialized data structures like segment trees or balanced trees may be better. Also, if the window size changes dynamically, this method becomes complex and less efficient.

Production Patterns

Used in real-time analytics for monitoring maximum sensor readings, stock price tracking over time windows, and in competitive programming for efficient sliding window queries.

Connections

Monotonic Queue

Sliding Window Maximum uses a monotonic queue pattern to maintain order of elements.

Understanding monotonic queues helps generalize sliding window problems to minimums, sums, or other aggregates.

Segment Tree

Both solve range query problems but segment trees handle dynamic updates and multiple query types.

Knowing sliding window maximum clarifies when simpler deque-based methods suffice versus when complex trees are needed.

Real-Time Signal Processing

Sliding window maximum algorithms are applied to analyze moving peaks in signals.

Recognizing this connection shows how data structures impact practical fields like engineering and physics.

Common Pitfalls

#1 Removing elements from the front of the deque without checking if they are out of the current window.

Wrong approach:

if (!dq.empty() && dq.front() < i) { dq.pop_front(); }

Correct approach:

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

Root cause:

Confusing the condition for removing outdated indices leads to removing valid maximums prematurely.

#2 Storing values instead of indices in the deque.

Wrong approach:

deque.push_back(nums[i]); // storing values

Correct approach:

deque.push_back(i); // storing indices

Root cause:

Not realizing that indices are needed to check window boundaries causes incorrect maximum calculations.

#3 Not removing smaller elements from the back before adding a new element.

Wrong approach:

deque.push_back(i); // without popping smaller elements

Correct approach:

while (!deque.empty() && nums[deque.back()] < nums[i]) { deque.pop_back(); } deque.push_back(i);

Root cause:

Failing to maintain decreasing order in deque leads to incorrect maximums and inefficient performance.

Key Takeaways

Sliding Window Maximum Using Deque efficiently finds maximums in all windows by maintaining a deque of indices in decreasing order of values.

Storing indices instead of values in the deque is crucial to track window boundaries and maintain correctness.

Each element is pushed and popped at most once, making the algorithm run in linear time O(n).

Removing smaller elements from the back ensures the front of the deque always holds the maximum for the current window.

Understanding this technique enables solving many real-time and large-scale data problems efficiently.

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