<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>

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        medianFinder = MedianFinder()
        res = []

        for i, num in enumerate(nums):
            if i >= k:
                medianFinder.delNum(nums[i-k])
            medianFinder.addNum(num)
            if i >= k-1:
                res.append(medianFinder.findMedian())
        
        return res

class MedianFinder:

    def __init__(self):
        self.left = [] # maxHeap
        self.right = [] # minHeap
        self.balance = 0 # if -ve left is heavy, +ve right is heavy
        self.removed = defaultdict(int)

    def cleanup(self):
        while self.left and self.removed[-self.left[0]] > 0:
            r = -heapq.heappop(self.left)
            self.removed[r] -= 1
            
        while self.right and self.removed[self.right[0]] > 0:
            r = heapq.heappop(self.right)
            self.removed[r] -= 1

        self.balanceHeaps()

    def balanceHeaps(self):
        # balance the weights
        if self.balance > 1:
            # if right heap is too heavy, move to left heap
            heapq.heappush(self.left, -heapq.heappop(self.right))
            self.balance -= 2
        elif self.balance < -1:
            # if left heap is too heavy, move to right heap
            heapq.heappush(self.right, -heapq.heappop(self.left))
            self.balance += 2
        
        # balance the values
        if self.left and self.right and -self.left[0] > self.right[0]:
            heappush(self.right, -heappop(self.left))
            heappush(self.left, -heappop(self.right))

    def delNum(self, num):
        self.removed[num] += 1
        if self.left and num <= -self.left[0]:
            self.balance += 1
        elif self.right and num >= self.right[0]:
            self.balance -= 1
        self.cleanup()

    def addNum(self, num: int) -> None:
        self.balance -= 1
        heapq.heappush(self.left, -num) # heap push to left heap always
        
        self.balanceHeaps()

    def findMedian(self) -> float:
        self.cleanup()
        if self.balance < 0:
            # if left side is heavy, median will be at the top of the left heap
            return -self.left[0]
        elif self.balance > 0:
            # if right side is heavy, median will be at top of right heap
            return self.right[0]
        
        # if equal distribution, median will be avg of both tops
        return (-self.left[0] + self.right[0])/2

31365