โ† Amazon questions

Find minimum values in every sliding window of size w

Filed under Amazon

Free read 1 of 3

Confirm 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

  1. Confirm constraints on array size and whether negative numbers are allowed.

Solution

O(n) time, O(k) space

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