DSA: Sliding Window Maximum

Given an array and window size k, return the maximum of every contiguous window. Walk through the optimal approach.

Technical Reference & Key Concepts

The Challenge: Max of Every Window

Input: [1,3,-1,-3,5,3,6,7], k = 3. Output: [3,3,5,5,6,7]. Explain your approach and complexity before coding.

Core questions to address:

  1. Why is the naive approach O(n·k), and why does a max-heap not fully solve it?
  2. How does a monotonic deque give O(n)? What exactly do you store and what are the two removals?
  3. What is the invariant that makes the front of the deque always the current window's max?