Katkat
Back

Return the Maximum of Every Sliding Window

AmazonSoftware Engineer · HR Screen
HardSoftware EngineerHR ScreenCoding & Algorithms

Last updated

This problem tests your ability to maintain a sliding window maximum using an efficient data structure like a deque to achieve linear time complexity.

Sliding Window Maximum

Given an integer array nums and a positive integer k, representing the size of a sliding window that moves from the far left of the array to the far right, return the maximum value for each window position. The window moves one position to the right at each step.

Function Signature

def max_sliding_window(nums: list[int], k: int) -> list[int]:

Constraints

  • 1 <= nums.length <= 10^5
  • `-10^4 max is 3
  • Window [3, -1, -3] -> max is 3
  • Window [-1, -3, 5] -> max is 5
  • Window [-3, 5, 3] -> max is 5
  • Window [5, 3, 6] -> max is 6
  • Window [3, 6, 7] -> max is 7

Example 2: Input: nums = [1], k = 1 Output: [1]

Edge Cases

  • k = 1 (The output should be the original array).
  • Array size equals k (Return the maximum of the entire array).
  • Array with all identical elements or strictly increasing/decreasing values.

Hints

Hint 1

A brute force approach would involve scanning the window for every position, resulting in O(n * k) complexity; can we do better?

Hint 2

Consider using a double-ended queue (deque) to store indices of potential maximums in a way that the front of the queue is always the index of the current window's maximum.

Hint 3

When moving the window, remove indices from the front if they are out of the window range and remove indices from the back if their values are less than the current element being processed.

Follow-up questions

  • How would you modify your solution to return the sliding window *minimum* instead of the maximum?
  • What is the time and space complexity of your optimized solution, and can you explain why?
  • If the input array were too large to fit into memory, how would you approach this problem?