Show problems as
Classic problem #480HardArrayHash TableSliding WindowHeap (Priority Queue)Treap

Sliding Window Median

Real-world version: Rolling Frame Middle
Tracked in this browser only
Read Sliding Window Median on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A monitor logs one integer per tick into readings. A frame of span consecutive readings starts at the left end and slides right one tick at a time, so the first frame covers positions 0 through span - 1, the next covers 1 through span, and so on until the frame reaches the right end.

The middle value of a frame is defined on the frame's readings put in sorted order. When span is odd it is the single reading in the centre. When span is even it is the mean of the two central readings, so it can land halfway between two integers and must be reported that way, for example 5.5.

Return the middle value of every frame, in the order the frames appear.

Examples

Example 1

Input
readings = [4,1,7,1,8], span = 3
Output
[4.0,1.0,7.0]

The three frames sort to [1,4,7], [1,1,7] and [1,7,8], and the centre entry of each is 4, 1 and 7.

Example 2

Input
readings = [6,2,9,4], span = 2
Output
[4.0,5.5,6.5]

Every frame holds two readings, so each answer is their mean: 4 for 6 and 2, 5.5 for 2 and 9, and 6.5 for 9 and 4.

Constraints

  • 1 <= span <= readings.length <= 10^5
  • -2^31 <= readings[i] <= 2^31 - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def rolling_medians(readings: list[int], span: int) -> list[float]:
Java
public double[] rollingMedians(int[] readings, int span)

More on the same topics