Sliding Window Maximum (Deque)

This article covers the intuition, workflow, dry run, C++ implementation, complexity, and interview usage for Sliding Window Maximum (Deque).

1. Intuition

For each window, you need the maximum quickly. A deque keeps indices in decreasing value order, so the front is always the maximum of the current window.

2. How It Works

1. Remove indices that fall out of the window
2. Remove smaller values from the back
3. Push the current index
4. Once the first full window forms, record the front value

3. Pattern Recognition

Think deque when you see:

• max or min of every fixed-size window
• online window extrema

4. Dry Run Example

Input:

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Step-by-step execution:

• First window [1, 3, -1] gives 3
• Next windows give 3, 5, 5, 6, 7

Final Output:

[3, 3, 5, 5, 6, 7]

5. Code (C++)

vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
  deque<int> dq;
  vector<int> answer;

  for (int i = 0; i < static_cast<int>(nums.size()); i++) {
    while (!dq.empty() && dq.front() <= i - k) {
      dq.pop_front();
    }

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

    dq.push_back(i);

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

  return answer;
}

6. Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(k)

7. When to Use

• every-window max or min
• queue with monotonic order

8. Common Mistakes

• storing values instead of indices
• forgetting to evict out-of-window indices first

9. Variations / Extensions

• sliding window minimum
• shortest subarray with monotonic deque

10. LeetCode Practice Problems

Hard

• https://magicsheet.dev/questions/sliding-window-maximum/

11. Key Takeaways

• Deque gives O(1) amortized access to current best candidate
• The front is the answer, the back is where cleanup happens

Back: Stack, Queue, and Heap Patterns