Largest and smallest median over sliding windows

You are given an integer array nums and a window length k. Slide a window of k consecutive elements across the array. For every window take its median; when k is even, use the lower of the two middle values. Return the largest and the smallest of these medians.

Interface

Unless you agree on a different interface with the interviewer, assume:

• median_extremes(nums: list[int], k: int) -> list[int] — returns [max_median, min_median], or [] when k > len(nums).

The median of a window is its element at sorted index (k - 1) // 2.

Example

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3  ->  [6, -1]
# window medians: 1, -1, -1, 3, 5, 6
nums = [4, 1, 3, 2], k = 2                ->  [2, 1]
# lower medians of [4, 1], [1, 3], [3, 2]: 1, 1, 2
nums = [5, 2, 8, 1], k = 1                ->  [8, 1]

Constraints

• 0 <= len(nums) <= 10^5, -10^9 <= nums[i] <= 10^9
• Aim for O(n log k) time and O(k) extra space.

Clarifying questions

• Are the k elements consecutive, or any k elements in order?
• For even k: the lower middle, the upper middle or their average?
• What to return when k is larger than the array?
• Can values repeat?

What a strong answer covers

• The brute force (sort each window, O(n k log k)) and why it is too slow.
• Keeping the window in an ordered structure so each slide is O(log k): two heaps with lazy deletion, a sorted list with binary-search insert and delete, or a Fenwick tree over compressed values.
• Reading the element at index (k - 1) // 2 after every slide and keeping a running max and min.
• Removing the right copy when values repeat; tests with k = 1, k = n and an even k.

Follow-ups

• The k elements no longer need to be consecutive: any subsequence of length k. What are the largest and smallest medians now, and why does sorting the array answer it?
• Return the sum of all window medians.
• Values arrive as a stream; report the median of the last k values after each one.