The median over a window
A meteorologist smooths a series of daily temperatures with a running median: for each window of w consecutive days, take the middle day by value. Unlike the arithmetic mean, the median is not shifted by one anomalous thaw or a sensor error. If the window has an even number of days, take the lower median, the smaller of the two middle ones.
Two tests are the real daily mean temperature of Almaty from 1 January 1941 to 31 December 2025 in tenths of a degree, 31,046 days, with a window of a year and of a month.
Input
The first line holds n and w (1 ≤ w ≤ n ≤ 100,000). The second holds n integers a1, …, an, |ai| ≤ 10⁹.
Output
n − w + 1 numbers, one per line: for each i from 1 to n − w + 1, the element at position ⌊(w + 1)/2⌋ (counting from one) if the numbers ai, …, ai+w−1 are sorted in increasing order.
Examples
Example 1
8 3 5 -3 8 8 1 -7 4 9
5 8 8 1 1 4
Example 2
7 4 2 2 7 2 7 7 1
2 2 7 2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Without deletions the problem is well known: the median of a stream is kept by two heaps, the lower one with the smaller half of the numbers and the largest on top, the upper one with the larger half and the smallest on top. The median is the top of the lower one. What gets in the way here?
2Hint 2
A day that has left the window may lie deep in either heap. Do not look for it there; delete it lazily: mark it and throw it away when it reaches the top. But then the heap sizes lie. What do you need to count separately?
3Hint 3
Equal temperatures make it hard to tell which heap the departing day is in. Make all keys distinct.
4The idea
The key of day i is the pair (value, i): there are no equal keys any more, and all live keys of the lower heap are smaller than all live keys of the upper one. Then a departing day lies in the lower heap exactly when its key is no greater than that heap's live top. Count the live keys in each heap separately; a deletion is a mark plus a decrement of its heap's counter. Marked keys are thrown away only when they are on top. After each step rebalance the heaps so that the lower one has ⌊(w + 1)/2⌋ live keys; its top is the lower median.
5Walkthrough
The pair (value, i) is conveniently packed into one number: (ai + 10⁹)·n + i. Such numbers are ordered like the pairs, the day number is recovered as the remainder of division by n, and the value as the quotient minus 10⁹. The lower heap stores keys negated, so that heapq and container/heap keep the largest on top.
The step for day i: push its key into the lower heap if it is less than that heap's live top, otherwise into the upper one. If day i − w has left the window, find out which heap it is in (compare it with the live top of the lower heap before marking it), decrement that heap's counter and mark the day. Then move the live top from heap to heap until the lower one has exactly ⌊(k + 1)/2⌋ live keys, where k is how many days are in the window now. The “live top” function first throws marked keys off the top, then returns the top.
There is also a solution without heaps: keep the window as a sorted list, delete the departing day and insert the new one in place by binary search (bisect.insort). Each step costs O(w), but it is a single memory shift, and, as the measurement in the article shows, such shifts are very fast: with n up to 100,000 this solution fits in the limits, on the fifth test five times slower than the heaps. On a series of tens of millions of values with a window of a million, the shifts would lose to the heaps hundreds of times over.
The garbage in the heaps is bounded: each day enters a heap once and is thrown out of it once. Even if marked keys get stuck deep inside for a long time, a heap is no larger than n.
5+Solution
6Complexity
Each day costs a few heap operations, each O(log n); throwing away marked keys costs O(n log n) over the whole pass. In total O(n log n) time and O(n) memory.
7Common mistakes
- Sorting every window. O(n · w log w): the fifth test has fifty thousand windows of fifty thousand days.
- Marking first, then deciding where it lay. If the departing day was the live top of the lower heap, throwing away marked keys removes it, and the comparison with the new top sends its count to the wrong heap.
- Comparing by value without the day number. It can be done, but then with equal temperatures “lies in the lower heap” no longer follows from the comparison, and the counters have to be kept differently, through the difference of sizes. Keys with the day number remove the question entirely.
- The upper median instead of the lower. With an even w in the second sample the smaller of the two middle values is needed: the lower heap must hold ⌊(w + 1)/2⌋ keys, not ⌊w/2⌋.