Twice-the-Median of Every Window Along a Sensor Trace
Implement windowTwiceMedians
A sensor produces a trace of integer readings. For every window of k consecutive readings, report twice the median of the window (so the answer is always an integer): for an odd k that is twice the middle value, and for an even k it is the sum of the two middle values.
Sorting each window separately repeats a lot of work, since consecutive windows share all but one reading. Two heaps — a max-heap for the smaller half and a min-heap for the larger half — keep the median at their roots. Because a heap can't delete an arbitrary element cheaply, readings that slide out of the window are only marked expired and quietly discarded when they reach the top.
Example 1:
Input: readings = [5,2,9,1,7], k = 3
Output: [10,4,14]
Example 2:
Input: readings = [4,4,4,4], k = 2
Output: [8,8,8]
Example 3:
Input: readings = [3,-3,8], k = 1
Output: [6,-6,16]
+ 11 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ k ≤ readings.length ≤ 60 - ●
-1000 ≤ readings[i] ≤ 1000, and readings may repeat - ●
For every window of k consecutive readings (left to right), report twice the median: for an odd k this is 2 × the middle value; for an even k it is the sum of the two middle values - ●
Return the answers in window order — readings.length − k + 1 of them
readings =
k =