Rolling Median of a Signal
Medians are a robust way to smooth noisy metrics. Given an array nums and a window size k, slide a window of k consecutive elements from left to right and return the median of each window.
For odd k the median is the middle value of the sorted window. For even k it is the average of the two middle values (which may be a fraction). If nums has fewer than k elements, return an empty array.
Example 1
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1,-1,-1,3,5,6]
Example 2
Input: nums = [1,2,3,4], k = 2 Output: [1.5,2.5,3.5]
Constraints
- 0 <= nums.length <= 10^4
- 1 <= k <= 10^4
- -2^31 <= nums[i] <= 2^31 - 1
Hint 1
Keep the current window in sorted order; binary search tells you where to insert and remove.
Hint 2
An alternative is two heaps (a max-heap for the lower half, a min-heap for the upper half) with lazy deletion.
Good practice for: Data Scientist, Machine Learning Engineer, Data Engineer, Site Reliability Engineer, Embedded Systems Engineer, MLOps Engineer
Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.