hardHeap / Priority QueueAI-applied~50 min
Rolling Window Median Latency
An inference service samples per-request latency. A dashboard shows the median latency over the most recent k requests, sliding one request at a time. Emit the median for every window position.
Problem
Given an integer array nums and a window size k, return the median of each contiguous window of size k as the window slides from left to right. The median of an even-sized window is the average of the two middle values.
Input
An array nums of n integers (1 ≤ k ≤ n ≤ 10^5, values fit in 32 bits).
Output
An array of n−k+1 doubles, one median per window.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- Values can be any 32-bit integer (watch overflow in averaging)
- Each window slides by one position
Examples
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]
Median of each size-3 window as it slides.
Example 2
Input
nums = [1,2,3,4], k = 2
Output
[1.5, 2.5, 3.5]
Even windows average the two middle elements.