Sliding Window Maximum — Problem Statement & Solution Guide
Problem Description
Given an array of integers and an integer k, find the maximum element in each window of size k.
Examples
Input
[1, 3, -1, -3, 5, 7, 8, 12]
Output
[3, 5, 7]
Explanation: Step-by-step: with input [1, 3, -1, -3, 5, 7, 8, 12], we initialize a deque to store indices of the maximum elements in the current window. We iterate through the array, and for each element, we remove the indices of elements that are out of the current window from the deque. We then add the index of the current element to the deque and update the maximum element in the current window. We append the maximum element in the current window to the result array. Finally, we return the result array.
Input
[5, 7, 8, 12, 15]
Output
[7]
Explanation: Step-by-step: with input [5, 7, 8, 12, 15], we initialize a deque to store indices of the maximum elements in the current window. We iterate through the array, and for each element, we remove the indices of elements that are out of the current window from the deque. We then add the index of the current element to the deque and update the maximum element in the current window. We append the maximum element in the current window to the result array. Finally, we return the result array.
Constraints
- 1 <= n <= 10^5
- 1 <= k <= n
- -10^4 <= arr[i] <= 10^4
Optimal Approach & Strategy
Use Deque. Store indices. Remove indices out of window bounds. Remove indices whose values are <= current value (they can never be max). Add current index. Deque front always holds max for current window. Time O(N), Space O(K).
Brute Force Approach
Find max for every window linearly. Time O(N*K).
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.