I understand that the solution says it’s in O(nk), the O(k) part is because we have to find an element to remove from the heap which is the leftmost element in the sliding window.
Can’t we instead of removing an element, insert the value into the minHeap median - element_to_remove, that way we will keep the number parity (even or odd) of the window and keep the median of the distribution intact.
The current implementation uses maxHeap.size(). If you aren’t going to remove the elements from the heap, how are you going to modify this logic?