Sliding Window Median

The median 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.

• For examples, if arr = [2,3,4], the median is 3.
• For examples, if arr = [1,2,3,4], the median is (2 + 3) / 2 = 2.5.

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

Return the median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.

Example 1:

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

Example 2:

Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Constraints:

• 1 <= k <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

class Solution:
    def medianSlidingWindow(self, nums: list[int], k: int) -> list[float]:
        import heapq
        
        medians = []
        window = sorted(nums[:k])
        
        if k % 2 == 0:
            median = (window[k//2 - 1] + window[k//2]) / 2
        else:
            median = window[k//2]
            
        medians.append(median)
        
        for i in range(k, len(nums)):
            # Remove nums[i-k] from window
            window.remove(nums[i-k])
            
            # Insert nums[i] into window
            import bisect
            bisect.insort(window, nums[i])
            
            if k % 2 == 0:
                median = (window[k//2 - 1] + window[k//2]) / 2
            else:
                median = window[k//2]
            
            medians.append(median)
            
        return medians

Explanation:

1. Initialization:

   • medians: An empty list to store the median of each sliding window.
   • window: The initial sliding window of size k from the input array nums, sorted in ascending order.

2. First Median Calculation:

   • Calculates the median of the initial window.
   • If k is even, the median is the average of the two middle elements.
   • If k is odd, the median is the middle element.
   • Appends the calculated median to the medians list.

3. Sliding Window Iteration:

   • Iterates through the array nums from index k to the end.
   • In each iteration:
     • Removes the element that is going out of the window (i.e., nums[i-k]) from the sorted window.
     • Inserts the new element entering the window (i.e., nums[i]) into the correct position in the sorted window using bisect.insort() to maintain the sorted order.
     • Calculates the median of the updated window as before.
     • Appends the calculated median to the medians list.

4. Return:

   • Returns the list medians containing the median of each sliding window.

Example:

For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3:

1. Initial window: [1, 3, -1]

   • Sorted window: [-1, 1, 3]
   • Median: 1

2. Next window: [3, -1, -3]

   • Sorted window: [-3, -1, 3]
   • Median: -1

3. And so on...

Big(O) Time Complexity Analysis:

• O(n*k) - The solution involves sorting the window which takes O(k log k) time and repeating the sorting operation n-k times which yields O(nklogk). Removing an element also takes O(k) time because window.remove is O(n). Thus, the entire operation is O(nk)

Big(O) Space Complexity Analysis:

• O(k) - The solution stores the sliding window with size k. Thus, it takes O(k) space.