379. Sliding Window Median
The median of a list is its middle value once the list is sorted: the exact middle element when the length is odd, and the average of the two middle elements when the length is even.
You are given an integer array nums and a window size k. Slide a window of length k across nums from left to right, one position at a time, and compute the median of each window. Return the medians in order — an array of n − k + 1 values.
So that the output is canonical, every median is printed with exactly one digit after the decimal point: an odd-window median like 3 prints as 3.0, and even-window medians always end in .0 or .5 because they average two integers.
Example 1:
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
Explanation: The first window [1, 3, -1] sorts to [-1, 1, 3], so its median is 1. Sliding one step gives [3, -1, -3] → sorted [-3, -1, 3] → median -1, and so on through [3, 6, 7] → median 6.
Example 2:
Input: nums = [1, 2, 3, 4], k = 2
Output: [1.5, 2.5, 3.5]
Explanation: With k = 2 every window has even length, so each median is the average of its two values: (1+2)/2 = 1.5, (2+3)/2 = 2.5, (3+4)/2 = 3.5.
Constraints:
- 1 ≤ k ≤ nums.length ≤ 10⁵
- -2³¹ ≤ nums[i] ≤ 2³¹ - 1
Hints:
Re-sorting every window from scratch repeats almost identical work — consecutive windows share k − 1 of their elements. What data structure lets you keep the window 'always ready' to report a median as elements enter and leave?
Split the window into two balanced halves: a max-heap holding the smaller half and a min-heap holding the larger half — the median lives at their tops. Heaps cannot delete an arbitrary element, so record outgoing values in a 'delayed' counter and physically discard them only when they surface at a heap top, while tracking how many *valid* elements each side holds.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Expected output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]