JavaScriptHardStack & Queue35 min
Find the maximum in every sliding window
Return the maximum value of each consecutive window of k integers. All input is valid JSON satisfying the constraints; do not mutate the meaning of values through type coercion. Interviewers use this problem to assess keep a decreasing deque of candidate indices.
Input
A JSON object {"array": [...], "k": integer}.
Output
Print one compact JSON value: an array of window maxima.
Constraints
1 <= array length <= 10000; 1 <= k <= array length; integer elements between -1000000 and 1000000.
Example
Input
{"array":[1,3,-1,-3,5,3,6,7],"k":3}Output
[3,3,5,5,6,7]
Example 2 input
{"array":[1,2,3],"k":1}Output
[1,2,3]
Boundary case: Each index enters and leaves the deque at most once
Public test cases (2)
Input
{"array":[1,3,-1,-3,5,3,6,7],"k":3}Expected output
[3,3,5,5,6,7]
Input
{"array":[2,2,1],"k":2}Expected output
[2,2]
Hints (2)
- Discard indices outside the window
- Each index enters and leaves the deque at most once
Target complexity: time O(n) · space O(n), including output and the index buffer