Twice-the-Median of Every Window Along a Sensor Trace

Hard40–45 min

Topics

HeapTwo HeapsSliding WindowLazy Deletion

Companies

GoogleAmazonMicrosoftBloomberg

A sensor produces a trace of integer readings. For every window of k consecutive readings, report twice the median of the window (so the answer is always an integer): for an odd k that is twice the middle value, and for an even k it is the sum of the two middle values.

Sorting each window separately repeats a lot of work, since consecutive windows share all but one reading. Two heaps — a max-heap for the smaller half and a min-heap for the larger half — keep the median at their roots. Because a heap can't delete an arbitrary element cheaply, readings that slide out of the window are only marked expired and quietly discarded when they reach the top.

Test Case 1:

Input:readings = [5, 2, 9, 1, 7], k = 3

Output:[10, 4, 14]

Explanation:Windows [5,2,9] → sorted [2,5,9], median 5 → 10. [2,9,1] → [1,2,9], median 2 → 4. [9,1,7] → [1,7,9], median 7 → 14.

Test Case 2:

Input:readings = [4, 4, 4, 4], k = 2

Output:[8, 8, 8]

Explanation:Each window of two 4s has middle values 4 and 4, so twice the median is 8.

Test Case 3:

Input:readings = [3, -3, 8], k = 1

Output:[6, -6, 16]

Explanation:With k = 1 every window is a single reading, so the answer is simply twice each reading.

Constraints

◆1 ≤ k ≤ readings.length ≤ 60
◆-1000 ≤ readings[i] ≤ 1000, and readings may repeat
◆For every window of k consecutive readings (left to right), report twice the median: for an odd k this is 2 × the middle value; for an even k it is the sum of the two middle values
◆Return the answers in window order — readings.length − k + 1 of them

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Copy and Sort Every Window

Brute

For each of the n − k + 1 windows, copy its k readings, sort the copy, and read the middle: the doubled median is window[(k−1)/2] + window[k/2], which handles odd and even k alike. It is simple and correct, but every window is sorted from scratch even though consecutive windows share k − 1 readings.

TimeO(n · k log k)

SpaceO(k)

Java

Try it out

class Solution {
    public List<Integer> windowTwiceMedians(int[] readings, int k) {
        List<Integer> answers = new ArrayList<>();
        for (int start = 0; start + k <= readings.length; start++) {
            int[] window = Arrays.copyOfRange(readings, start, start + k);
            Arrays.sort(window);
            answers.add(window[(k - 1) / 2] + window[k / 2]);
        }
        return answers;
    }
}

Optimal — Two Heaps With Lazy Deletion

Optimal

Keep the window's smaller half in a max-heap (low) and larger half in a min-heap (high), with low holding the same number of readings as high or one more — so the median sits at the roots. Sliding the window means adding one reading and removing another, but heaps cannot delete an arbitrary element cheaply. Instead, deletion is lazy: mark the outgoing reading's index as expired, adjust the size of the heap it lives in (tracked in side[]), and only discard expired entries when they surface at a heap's top. Heaps store (value, index) pairs so an entry's expiry can be checked. After each slide, rebalance by moving valid tops between the heaps until the sizes are right, then read the median from the roots.

TimeO(n log n)

SpaceO(n)