Katkat
Back

Maximum of Fixed-Window Minimums

OracleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests the ability to compute sliding-window minima in linear time using a monotonic deque and determine the maximum value among those minima.

Maximum of Fixed-Window Minimums

Given an integer array nums and an integer k, consider every contiguous subarray (window) of length k. For each window, find its minimum element. Return the maximum value among all of these window minimums.

An optimal solution should run in O(n) time, where n is the length of nums.

Function Signature

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

Constraints

  • `1 <= k <= len(nums) min = -1
  • [3, -1, 5] -> min = -1
  • [-1, 5, 3] -> min = -1
  • [5, 3, 6] -> min = 3 The maximum among all window minimums [-1, -1, -1, 3] is 3.

**Example 2:**

```text
Input: nums = [4, 2, 5, 1], k = 1
Output: 5
Explanation:
For k = 1, each element is its own window minimum. The maximum element in the array is 5.

Edge Cases to Consider

  • k == 1: The answer is simply the maximum element of nums.
  • k == len(nums): The answer is the minimum element of nums.
  • Arrays containing strictly negative numbers or duplicate values.

Hints

Hint 1

A brute-force search that recomputes the minimum for each window takes O(n * k) time; consider how to maintain the current window's minimum in O(1) amortized time.

Hint 2

A monotonic double-ended queue (deque) storing indices in increasing order of values allows you to always access the minimum element of the current window from the front.

Hint 3

As the window slides, remove indices that fall outside the window from the front, pop larger elements from the back before inserting the current index, and update the global maximum once the first window of size k is formed.

Follow-up questions

  • How would you solve the problem if you were asked to find the maximum of window minimums for every possible window size from 1 to n?
  • Can you implement the sliding window minimum using two stacks instead of a deque while maintaining O(n) overall runtime?
  • How would you handle a real-time data stream where elements arrive continuously and k is extremely large?