<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]:
        # result = []
        # for i in range(len(nums) - k + 1):
        #     window = sorted(nums[i:i + k])
        #     if k % 2 == 1:
        #         median = window[k // 2] 
        #     else:
        #         median = (window[k // 2 - 1] + window[k // 2]) / 2.0 
        #     result.append(median)
        # return result

        medians = []
        hash_table = defaultdict(int)  # To keep track of elements to lazily delete
        lo = []  # Max-heap (inverted min-heap for Python)
        hi = []  # Min-heap
        
        # Helper function to balance heaps
        def balance_heaps():
            if len(lo) > len(hi) + 1:
                heapq.heappush(hi, -heapq.heappop(lo))
            elif len(hi) > len(lo):
                heapq.heappush(lo, -heapq.heappop(hi))
        
        # Helper function to remove invalid elements (marked in hash_table)
        def remove_invalid(heap, sign=1):
            while heap and hash_table[heap[0] * sign] > 0:
                hash_table[heap[0] * sign] -= 1
                heapq.heappop(heap)
        
        # Initialize the heaps
        for i in range(k):
            heapq.heappush(lo, -nums[i])
        
        for _ in range(k // 2):
            heapq.heappush(hi, -heapq.heappop(lo))
        
        # Slide the window
        for i in range(k, len(nums) + 1):
            # Calculate the median for the current window
            if k % 2 == 1:
                medians.append(-lo[0])
            else:
                medians.append((-lo[0] + hi[0]) / 2)
            
            if i == len(nums):
                break  # Exit if we have processed all elements
            
            # Incoming and outgoing elements
            out_num = nums[i - k]
            in_num = nums[i]
            
            # Adjust balance based on whether the outgoing element is in lo or hi
            balance = 0
            if out_num <= -lo[0]:
                balance -= 1
            else:
                balance += 1
            
            # Mark outgoing element for lazy deletion
            hash_table[out_num] += 1
            
            # Insert new element into the appropriate heap
            if in_num <= -lo[0]:
                heapq.heappush(lo, -in_num)
                balance += 1
            else:
                heapq.heappush(hi, in_num)
                balance -= 1
            
            # Rebalance the heaps
            if balance < 0:
                heapq.heappush(lo, -heapq.heappop(hi))
            elif balance > 0:
                heapq.heappush(hi, -heapq.heappop(lo))
            
            # Remove elements that have been marked for lazy deletion
            remove_invalid(lo, -1)
            remove_invalid(hi, 1)
        
        return medians


30071