Given an array of integers and a window size k, return an array of the maximum value in each sliding window as it moves from left to right.
For example, given nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the output is [3, 3, 5, 5, 6, 7]. The windows are: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5, [-3,5,3]=5, [5,3,6]=6, [3,6,7]=7.
Explain your approach, why a naive approach is too slow, and how to achieve O(n) time complexity. Discuss the data structure you would use.
How to approach it
- Hint 1
A brute force approach scans each window for the max, giving O(n * k). Can you maintain the max more efficiently?
- Hint 2
A max-heap could track the maximum, but removing elements that leave the window is expensive.
- Hint 3
A monotonic deque (double-ended queue) stores indices of elements in decreasing order. Elements that can never be the maximum are discarded immediately.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.