PPractick

The problem

A network monitor reports, every second, the peak latency over the last k seconds. For a stream of n measurements, that's the maximum of every window of size k. Rescanning each window costs O(n · k). A monotonic deque of indices does it in O(n). The deque holds indices whose values are decreasing from front to back. A new value evicts every smaller-or-equal value from the back, since those can never be a window's maximum again. The front drops out when it leaves the window. The front is always the current maximum.

Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7].

Function signature

vector<int> maxSlidingWindow(const vector<int>& nums, int k);  // 1 <= k <= n

Test cases

Input (nums, k)	Output	Explanation
([1, 3, -1, -3, 5, 3, 6, 7], 3)	[3, 3, 5, 5, 6, 7]
([1], 1)	[1]
([9, 8, 7, 6], 2)	[9, 8, 7]	Decreasing: the maximum expires each step
([1, 2, 3, 4], 4)	[4]	One window
([4, 4, 4], 2)	[4, 4]

(Confirm: windows are contiguous, of size exactly k; there are n − k + 1 outputs.)

How interviewers phrase it

• "Return the max of each sliding window of size k" (LeetCode 239).

Clarifying questions to ask

1. Is k always between 1 and n?
2. How large are n and k? (Up to 10⁵, so O(n · k) is too slow.)
3. Can values repeat or be negative? (Yes.)

Follow-ups to expect

1. "Why store indices, not values?"
2. "Why pop smaller values from the back?"
3. "Why is it O(n)?"
4. "Other approaches?"
5. "Sliding window minimum?"

Related questions

• Longest Repeating Character Replacement Hard
• Binary Subarrays With Sum Hard
• Count number of Nice subarrays Hard
• Number of Substrings Containing All Three Characters Hard
• Longest Substring With At Most K Distinct Characters Hard
• Minimum Window Substring Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in