Find minimum values in every sliding window of size w
Filed under Amazon
Free read 1 of 3Confirm constraints on array size and whether negative numbers are allowed.
The question
Given an array of integers and a sliding window size w moving from left to right, output the minimum element present in each window position in O(n) total time.
Constraints
- 1 <= w <= n <= 10^5
- -10^9 <= arr[i] <= 10^9
Examples
- Input
- arr = [1, 3, -1, -3, 5, 3, 6, 7], w = 3
- Output
- [-1, -3, -3, -3, 3, 3]
- Why
- Min values for windows of size 3 across the array.
Approach
Confirm constraints on array size and whether negative numbers are allowed.
Iterate through every possible window of size w and scan for the minimum, taking O(n * w) time.
Use a monotonic double-ended queue (deque) storing indices. Maintain elements in increasing order of their values, popping elements out of bounds or larger than the current element.
Window size w greater than array length n, or w = 1.
Solution
O(n) time, O(k) space
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
dq = deque()
res = []
for i, val in enumerate(nums):
if dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] > val:
dq.pop()
dq.append(i)
if i >= k - 1:
res.append(nums[dq[0]])
return res
Tips
- What they are testing: Test with window size 1, window size equal to array length, and strictly decreasing or increasing arrays.
- Common mistake: Using a min-heap without lazy deletion, or a BST which yields O(n log w) time complexity instead of the required O(n).
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.