Sliding Window Median

Sliding Window Median

What is this problem about?

Similar to the "Sliding Window Maximum" problem, the "Sliding Window Median" interview question involves a window of size k moving across an array. However, instead of the maximum, you must find the median of the k numbers in the window at each step. This "Sliding Window Median coding problem" is significantly harder because the median is the middle element in a sorted list, and maintaining a sorted list while adding and removing elements is computationally expensive.

Why is this asked in interviews?

Companies like Apple, Microsoft, and Meta use this to test a candidate's mastery of advanced data structures. It requires you to balance two priority queues (heaps) or use a balanced BST. It evaluates your ability to handle insertions, deletions, and rebalancing in O(log k) time. This problem is a true test of whether you can optimize complex operations within a sliding window framework.

Algorithmic pattern used

The "Two Heaps (Priority Queues) and Sliding Window interview pattern" is the standard O(N log K) approach.

1. Use a max-heap to store the smaller half of the numbers and a min-heap for the larger half.
2. For each window:
   • Add the new element to the appropriate heap and rebalance so their sizes differ by at most one.
   • The median is either the top of the larger heap or the average of the two tops.
3. The tricky part is "lazy removal": since standard heaps don't support removing arbitrary elements, you keep track of elements to be removed in a hash map and remove them only when they reach the top of a heap.

Example explanation

Array: [1, 3, -1, -3, 5], k=3

1. Window [1, 3, -1]: Sorted is [-1, 1, 3]. Median is 1.
2. Window [3, -1, -3]: Sorted is [-3, -1, 3]. Median is -1.
3. Window [-1, -3, 5]: Sorted is [-3, -1, 5]. Median is -1. Final result: [1, -1, -1]. Maintaining this without full re-sorting is the key challenge.

Common mistakes candidates make

A major pitfall is attempting to re-sort the entire window at every step, which is O(N * K log K). Another common error is failing to handle the removal of elements correctly when they leave the sliding window. Precision errors with floating-point math when calculating the average of two numbers (if k is even) can also occur. Many candidates also forget to keep the two heaps balanced in terms of size.

Interview preparation tip

The "Two Heaps" pattern is a classic for finding the "Median from Data Stream." For the "Sliding Window Median interview question", you just add the deletion logic. Practice the "lazy deletion" technique with a frequency map to handle standard priority queue limitations in languages like C++ or Java.