<p>The <strong>median</strong> is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.</p>

<ul>
	<li>For examples, if <code>arr = [2,<u>3</u>,4]</code>, the median is <code>3</code>.</li>
	<li>For examples, if <code>arr = [1,<u>2,3</u>,4]</code>, the median is <code>(2 + 3) / 2 = 2.5</code>.</li>
</ul>

<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. There is a sliding window of size <code>k</code> which is moving from the very left of the array to the very right. You can only see the <code>k</code> numbers in the window. Each time the sliding window moves right by one position.</p>

<p>Return <em>the median array for each window in the original array</em>. Answers within <code>10<sup>-5</sup></code> of the actual value will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,-1,-3,5,3,6,7], k = 3
<strong>Output:</strong> [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
<strong>Explanation:</strong> 
Window position                Median
---------------                -----
[<strong>1  3  -1</strong>] -3  5  3  6  7        1
 1 [<strong>3  -1  -3</strong>] 5  3  6  7       -1
 1  3 [<strong>-1  -3  5</strong>] 3  6  7       -1
 1  3  -1 [<strong>-3  5  3</strong>] 6  7        3
 1  3  -1  -3 [<strong>5  3  6</strong>] 7        5
 1  3  -1  -3  5 [<strong>3  6  7</strong>]       6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,2,3,1,4,2], k = 3
<strong>Output:</strong> [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

from sortedcontainers import *

def compute_median(max_heap, min_heap, k):
    if k % 2 == 0:
        return (-max_heap[0] + min_heap[0]) / 2

    return -max_heap[0]    

class Solution:

    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        n = len(nums)
        k = min(k, n)

        # max heap to hold the bottom k//2 items
        max_heap = []

        # min heap to hold the top k//2 items
        min_heap = []
    
        # dictionary for holding the removed items that are still in the heaps
        removed_nums = defaultdict(int)

        # variable to store the number of removed items that are still present in the max_heap
        removed_items_max_heap = 0

        # variable to store the number of removed items that are still present in the min_heap
        removed_items_min_heap = 0

        # initialize the min_heap and max_heap so that max_heap has k/2 smallest items and min_heap has the k/2 largest items 
        max_heap = [ -x for x in nums[:k] ]
        heapify(max_heap)

        for i in range(k//2):
            heappush(min_heap, -heappop(max_heap))

        # print(max_heap, min_heap)
        result = [compute_median(max_heap, min_heap, k)]

        for i in range(k, n):

            # get the item that is leaving the window
            removed_num = nums[i-k]
            removed_nums[removed_num] += 1

            # determine if the number leaving the window in in the max heap or min heap
            if removed_num <= -max_heap[0]:
                removed_items_max_heap += 1
            elif removed_num >= min_heap[0]:
                removed_items_min_heap += 1

            # push the new item into the min or max heap
            if nums[i] <= result[-1]:
                heappush(max_heap, -nums[i])
            else:
                heappush(min_heap, nums[i])

            # if the reballance the heaps
            if len(max_heap) - removed_items_max_heap > len(min_heap) - removed_items_min_heap + 1:
                heappush(min_heap, -heappop(max_heap))
            if len(max_heap) - removed_items_max_heap < len(min_heap) - removed_items_min_heap:
                heappush(max_heap, -heappop(min_heap))

            # pop any removed items off of the top of the max_heap
            while removed_items_max_heap > 0 and removed_nums[-max_heap[0]] > 0:
                removed_nums[-heappop(max_heap)] -= 1
                removed_items_max_heap -= 1

            # pop any removed items off of the top of the min_heap
            while removed_items_min_heap > 0 and removed_nums[min_heap[0]] > 0:
                removed_nums[heappop(min_heap)] -= 1
                removed_items_min_heap -= 1

            # compute median and add it to the result
            result.append(compute_median(max_heap, min_heap, k))

        return result

# 1,2,3,4,2,3,1,4,2
# k=3

# min_heap: (1,0), (2,1)
# max_heap: (3,2),
30934