Sliding Window Median - Solution & Explanation

The dual heap approach uses two heaps to maintain the sliding window median. The idea is to maintain a max heap for the left half of the data and a min heap for the right half. This allows for efficient retrieval of the median at any point:

• Use a max heap to store the smaller half of the numbers (lower part).
• Use a min heap to store the larger half of the numbers (upper part).
• When the window slides, update these heaps accordingly.
• The median can be extracted as the maximum from the max heap or by averaging the top of both heaps, depending on the window size (odd/even).

This Python solution uses the `SortedList` from the `sortedcontainers` module to maintain an ordered list of numbers in the current window. As the window slides:

• We add the new number and remove the one that's slid out.
• The list remains sorted, allowing easy median computation.
• The `SortedList` maintains order efficiently, ensuring operations stay logarithmic in nature.

This approach iteratively computes the median for each possible window by sorting the window at each step. This is a simpler approach but less efficient:

• For each window, extract the subarray.
• Sort this subarray to find the median.
• Move the window one element to the right and repeat.

This straightforward Python solution sorts each subarray individually to determine the median. The simplicity comes at the cost of performance for larger datasets:

• Sort the subarray extracted from nums starting at the current index.
• Compute the median based on the parity of k.
• Collect computed medians for all possible windows.

Use two heaps: a max-heap to keep track of the lower half of the window and a min-heap for the upper half. The max-heap stores the smaller half of numbers, while the min-heap stores the larger half. By maintaining the size property (balance) of these heaps, we can always pull the median based on the size of the window:

• When the sizes of both heaps are equal, the median is the mean of the top elements of both heaps.
• When the size of the max-heap is greater than the min-heap, the median is the top of the max-heap.

Efficient insertion and removal using heaps make this approach suitable for large inputs.

This solution defines three core functions: add_number to handle numbers entering the heap, remove_number deals with numbers leaving the heap, and balance_heaps keeps the two heaps balanced. The median is calculated based on the sizes of the heaps after adjusting them.

Using a balanced binary search tree structure (like C++ STL's multiset) that maintains order can help efficiently find medians. This approach utilizes iterators, which allow seamless tracking of median positions as we move the sliding window:

• Elements are inserted and removed from the multiset while the iterator always points to the median or close to it.
• The iterator is adjusted based on the balance between the lower and upper halves.

This Java implementation utilizes a TreeMap to store the elements of the current window. Functions to add and remove elements adjust the frequency count within the set, allowing us to maintain window data. getMedian then determines the median based on the current state of the window.