โ† Amazon questions

Sliding window maximum of all subarrays of size K

Filed under Amazon

Free read 2 of 3

Confirm 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

  1. Confirm constraints on array length and element value ranges.

Solution

O(N) time, O(K) space

Python
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.