Sliding Window Maximum Using Deque in DSA C++

Mental Model

Keep track of the largest elements in the current window using a special list that quickly removes smaller elements.

Analogy: Imagine a line of people waiting to buy tickets. Only the tallest people stay in line because shorter ones behind them can't be the tallest in the group. When the window moves, people who leave the group step out of the line.

Array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56]
Window size: 4
Deque stores indices of elements in decreasing order of their values
Example deque state:
Indices: 6 -> 7 -> 8 -> 9
Values:  8 -> 9 -> 10 -> 12
Window covers elements at indices 6 to 9

Dry Run Walkthrough

Input: array: [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], window size k=4

Goal: Find the maximum value in every window of size 4 as it slides from left to right

Step 1: Start with empty deque, process first element (2 at index 0)

Deque: [0]
Window: [2] (indices 0 to 0)

Why: Add first element index to deque as starting point

Step 2: Process element 1 at index 1, remove smaller elements from back

Deque: [0, 1]
Window: [2, 1] (indices 0 to 1)

Why: 1 is smaller than 2, so keep both; 1 might be max in future windows

Step 3: Process element 3 at index 2, remove smaller elements from back (1)

Deque: [0, 2]
Window: [2, 1, 3] (indices 0 to 2)

Why: 3 is bigger than 1, so remove 1; 3 is current max candidate

Step 4: Process element 4 at index 3, remove smaller elements from back (3)

Deque: [0, 3]
Window: [2, 1, 3, 4] (indices 0 to 3)

Why: 4 is bigger than 3, so remove 3; 4 is max in current window

Step 5: Window reached size 4, record max (value at deque front index 0 = 2)

Max so far: 2
Deque: [0, 3]

Why: Front of deque always holds index of max element in current window

Step 6: Slide window: process element 6 at index 4, remove smaller elements from back (4, 3, 1)

Deque: [4]
Window: [1, 3, 4, 6] (indices 1 to 4)

Why: 6 is bigger than 4, remove 4; 6 is new max candidate

Step 7: Remove indices out of window range (index 0 is out of window 1 to 4)

Deque: [4]
Window: [1, 3, 4, 6]

Why: Remove indices that are no longer in the current window

Step 8: Record max (value at deque front index 4 = 6)

Max so far: 2, 6
Deque: [4]

Why: Max for current window is at front of deque

Step 9: Process element 3 at index 5, smaller than 6, add to back

Deque: [4, 5]
Window: [3, 4, 6, 3] (indices 2 to 5)

Why: 3 is smaller than 6, keep both for future windows

Step 10: Slide window, remove indices out of range (index 1 out of window 2 to 5)

Deque: [4, 5]
Window: [3, 4, 6, 3]

Why: Remove indices no longer in window

Step 11: Record max (value at deque front index 4 = 6)

Max so far: 2, 6, 6
Deque: [4, 5]

Why: Max is at front of deque

Step 12: Process element 8 at index 6, remove smaller elements from back (3 at index 5, 6 at index 4)

Deque: [6]
Window: [4, 6, 3, 8] (indices 3 to 6)

Why: 8 is bigger than 3 and 6, remove them; 8 is new max candidate

Step 13: Slide window, remove indices out of range (index 2 out of window 3 to 6)

Deque: [6]
Window: [4, 6, 3, 8]

Why: Remove indices no longer in window

Step 14: Record max (value at deque front index 6 = 8)

Max so far: 2, 6, 6, 8
Deque: [6]

Why: Max is at front of deque

Step 15: Process element 9 at index 7, remove smaller elements from back (8 at index 6)

Deque: [7]
Window: [6, 3, 8, 9] (indices 4 to 7)

Why: 9 is bigger than 8, remove 8; 9 is new max candidate

Step 16: Slide window, remove indices out of range (index 3 out of window 4 to 7)

Deque: [7]
Window: [6, 3, 8, 9]

Why: Remove indices no longer in window

Step 17: Record max (value at deque front index 7 = 9)

Max so far: 2, 6, 6, 8, 9
Deque: [7]

Why: Max is at front of deque

Step 18: Process element 10 at index 8, remove smaller elements from back (9 at index 7)

Deque: [8]
Window: [3, 8, 9, 10] (indices 5 to 8)

Why: 10 is bigger than 9, remove 9; 10 is new max candidate

Step 19: Slide window, remove indices out of range (index 4 out of window 5 to 8)

Deque: [8]
Window: [3, 8, 9, 10]

Why: Remove indices no longer in window

Step 20: Record max (value at deque front index 8 = 10)

Max so far: 2, 6, 6, 8, 9, 10
Deque: [8]

Why: Max is at front of deque

Step 21: Process element 12 at index 9, remove smaller elements from back (10 at index 8)

Deque: [9]
Window: [8, 9, 10, 12] (indices 6 to 9)

Why: 12 is bigger than 10, remove 10; 12 is new max candidate

Step 22: Slide window, remove indices out of range (index 5 out of window 6 to 9)

Deque: [9]
Window: [8, 9, 10, 12]

Why: Remove indices no longer in window

Step 23: Record max (value at deque front index 9 = 12)

Max so far: 2, 6, 6, 8, 9, 10, 12
Deque: [9]

Why: Max is at front of deque

Step 24: Process element 56 at index 10, remove smaller elements from back (12 at index 9)

Deque: [10]
Window: [9, 10, 12, 56] (indices 7 to 10)

Why: 56 is bigger than 12, remove 12; 56 is new max candidate

Step 25: Slide window, remove indices out of range (index 6 out of window 7 to 10)

Deque: [10]
Window: [9, 10, 12, 56]

Why: Remove indices no longer in window

Step 26: Record max (value at deque front index 10 = 56)

Max so far: 2, 6, 6, 8, 9, 10, 12, 56
Deque: [10]

Why: Max is at front of deque

Result:

Final max values for each window: [2, 6, 6, 8, 9, 10, 12, 56]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<int> slidingWindowMax(const vector<int>& nums, int k) {
    deque<int> dq; // stores indices
    vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        // Remove indices out of current window
        while (!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); // Add current element index

        // Start adding max to result when first window is complete
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    vector<int> nums = {2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56};
    int k = 4;
    vector<int> max_values = slidingWindowMax(nums, k);

    for (int val : max_values) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

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

Remove indices that are out of the current window range

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

Remove smaller elements from the back to keep deque decreasing

dq.push_back(i);

Add current element index to deque

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

Add max element of current window to result

Output

2 6 6 8 9 10 12 56 

Complexity Analysis

Time: O(n) because each element is added and removed from the deque at most once

Space: O(k) because the deque stores indices of elements within the current window

vs Alternative: Naive approach checks all k elements for each window resulting in O(n*k) time, which is slower for large inputs

Edge Cases

Empty array

Returns empty result vector

DSA C++

for (int i = 0; i < nums.size(); ++i) {

Window size k is 1

Each element is the max of its own window, returns original array

DSA C++

if (i >= k - 1) {

Window size k equals array size

Returns single max value of entire array

DSA C++

while (!dq.empty() && dq.front() <= i - k) {

When to Use This Pattern

When asked to find maximum or minimum in every subarray or window of fixed size, use the sliding window maximum pattern with a deque to achieve efficient O(n) time.

Common Mistakes

Mistake: Not removing indices that are out of the current window range
Fix: Add a check to pop from front of deque when indices are outside the window

Mistake: Not removing smaller elements from the back before adding new element
Fix: Pop from back while elements are smaller than current to maintain decreasing order

Mistake: Adding max to result before the first full window is formed
Fix: Start adding max to result only when i >= k - 1

Summary

Finds the maximum value in every sliding window of size k efficiently using a deque.

Use when you need to quickly find max/min in all subarrays/windows of fixed size.

Keep a deque of indices in decreasing order of values, removing smaller and out-of-window 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