Rolling median across a sliding window

Question

Given a series and a window size k, report the median of each consecutive window of k values as the window slides one step at a time. The median is more robust to outlier prints than the mean. Return the list of window medians.

Accepted Answer

Keep the current window as a sorted list. Each slide removes the outgoing value and inserts the incoming one, both located by binary search, so the window stays sorted. The median is then a direct index lookup (middle element for odd k, average of the two middle for even k). Tracing k=3: the first window [-1,1,3] gives median 1; sliding to [-3,-1,3] gives -1, and so on to [3,6,7] giving 6. Time O(nk) here (the insert/delete shift is O(k)); a two-heap structure with lazy deletion reduces the per-step work toward O(log k). Space O(k). Edge cases: k = 1 echoes the input; even k averages two midd…

Rolling median across a sliding window

Your answer

More Coding questions