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

import heapq

class TwoHeapMedianFinder:

    def get_median(self) -> float:
        if (len(self.left_heap) + len(self.right_heap)) % 2 == 0:
            return (self.right_heap[0] - self.left_heap[0])/2
        else:
            return self.right_heap[0]

    def _get_median(self) -> tuple[float, list, list]:
        return self._get_median(), list(self.left_heap), list(self.right_heap)
    
    def __init__(self, init_list: List[int]):
        middle = len(init_list) // 2
        # python heapq default heap algorithms operate: min-heaps
        # so at the 0 index there will be the lowest element

        # left_heap - is max-heap made by making the values negative
        # so the biggest element can be found in left_heap as: -1*left_heap[0]
        sorted_list = sorted(init_list)
        self.left_heap = [-1*n for n in sorted_list[:middle]]
        self.right_heap = sorted_list[middle:]
        heapq.heapify(self.left_heap)
        heapq.heapify(self.right_heap)

    def _rebalance(self):
        if len(self.right_heap) > len(self.left_heap) + 1:
            lowest_right = heapq.heappop(self.right_heap)
            heapq.heappush(self.left_heap, -lowest_right)
        elif len(self.left_heap) > len(self.right_heap):
            highest_left = -heapq.heappop(self.left_heap)
            heapq.heappush(self.right_heap, highest_left)

    
    def add(self, n: int):
        if not self.right_heap or n >= self.right_heap[0]:
            heapq.heappush(self.right_heap, n)
        else:
            heapq.heappush(self.left_heap, -n)
        self._rebalance()
        
    def _remove_from_heap(self, heap: List[int], n: int):
        idx = heap.index(n)
        if idx < len(heap) - 1:
            heap[idx] = heap[-1]
            heap.pop()
            heapq._siftup(heap, idx)
            heapq._siftdown(heap, 0, idx)
        else:
            heap.pop()
           

    def remove(self, n: int):
        if n >= self.right_heap[0]:
            self._remove_from_heap(self.right_heap, n)            
        else:
            self._remove_from_heap(self.left_heap, -n)

        self._rebalance()


class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        median_finder = TwoHeapMedianFinder(nums[:k])
        
        res = [median_finder.get_median()]
        for i in range(k, len(nums)):
            median_finder.remove(nums[i - k])
            median_finder.add(nums[i])
        
            res.append(median_finder.get_median())
            
        return res


        
27771