PythonHardStack & Queue35 min
Find the maximum in every fixed-size window
Output windows from left to right. Equal values are allowed; each window contains exactly k elements. Interviewers use this problem to assess maintain only useful candidate indices in a monotonic deque.
Input
First line: n and k. Second line: n integers.
Output
Print the result values separated by single spaces; print an empty line for an empty result.
Constraints
1 <= k <= n <= 100000; -10^9 <= values <= 10^9.
Example
Input
8 3 1 3 -1 -3 5 3 6 7
Output
3 3 5 5 6 7
Example 2 input
5 2 5 4 3 2 1
Output
5 4 3 2
A decreasing array tests expiration of old maxima.
Public test cases (2)
Input
8 3 1 3 -1 -3 5 3 6 7
Expected output
3 3 5 5 6 7
Input
4 2 4 4 4 4
Expected output
4 4 4
Hints (2)
- Identify the state needed to avoid repeated work.
- Maintain only useful candidate indices in a monotonic deque.
Target complexity: time O(n) · space O(k) excluding the output