Sliding window maximum of all subarrays of size K
Filed under Amazon
Free read 2 of 3Confirm constraints on array length and element value ranges.
The question
Given an array of numbers and a window size k, find the maximum value in each sliding subarray window of length k from left to right.
Constraints
- 1 <= array.length <= 10^5
- 1 <= k <= array.length
- Time complexity should be O(N).
Examples
- Input
- nums = [1,3,-1,-3,5,3,6,7], k = 3
- Output
- [3,3,5,5,6,7]
- Why
- 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.
Approach
Confirm constraints on array length and element value ranges.
For each window, iterate through all k elements to find the maximum. Time complexity: O(N * K).
Use a monotonic decreasing deque storing indices. Remove elements smaller than the current element from the back, remove indices outside the current window from the front, and take the front as the max.
k equals 1, k equals array length, negative numbers.
Solution
O(N) time, O(K) space
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque()
res = []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if dq[0] == i - k:
dq.popleft()
if i >= k - 1:
res.append(nums[dq[0]])
return res
Tips
- What they are testing: Test with k=1, k=array length, and arrays with strictly decreasing or increasing elements.
- Common mistake: Using a max heap without lazy deletion, which degrades time complexity to O(N log N) in the worst case.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.