A monitor keeps a sliding window of the last w latency readings. For every contiguous window of exactly w consecutive readings (there are n - w + 1 of them, left to right), report the window's lower median: sort the window ascending as v[0] <= ... <= v[w-1] and take the element at 0-based index (w - 1) // 2.
Line 1: two integers n and w.
Line 2: n space-separated integers, the readings in order.
n - w + 1 space-separated integers on one line: the lower median of each window, left to right.
Example 1
Input
6 3 5 1 3 2 8 7
Expected
3 2 3 7
Explanation
Windows: [5,1,3]->3, [1,3,2]->2, [3,2,8]->3, [2,8,7]->7. Output: 3 2 3 7.
Example 2
Input
4 1 9 4 6 2
Expected
9 4 6 2
Explanation
With w=1 each window is a single reading, so the medians are the readings themselves: 9 4 6 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →