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.

&nbsp;
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]


&nbsp;
Constraints:


	1 &lt;= k &lt;= nums.length &lt;= 105
	-231 &lt;= nums[i] &lt;= 231 - 1


import bisect

class Solution:
    
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        
        half = int(k / 2)
        
        if k % 2 == 0:
            i, j = half - 1, half + 1
        else:
            i, j = half, half + 1
        
        def median(l, i, j):
            return sum(l[i:j])/len(l[i:j])
        
        digits = nums[:k]
        digits.sort()
        
        result = [median(digits, i, j)]
            
        for q in range(k, len(nums)):
            
            digits.remove(nums[q - k])
            bisect.insort(digits, nums[q])
            result.append(median(digits, i, j))   
            
        return result
class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        Queue<Integer> minHeap = new PriorityQueue<>();
        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        double[] res = new double[nums.length - k + 1];
        for(int i = 0; i< nums.length; i++){
            if(i >= k){
                if(!minHeap.remove(nums[i-k]))
                    maxHeap.remove(nums[i-k]);
            }

            // If k is odd, max heap is of odd size and min heap is of even
            // else both are of even size
            if(!maxHeap.isEmpty() && nums[i] <= maxHeap.peek()) {
                maxHeap.add(nums[i]);
                if(((k&1) == 1 && maxHeap.size() > k/2+1) || ((k&1) == 0 && maxHeap.size() > k/2)){
                    minHeap.offer(maxHeap.poll());
                }
            }else{
                minHeap.add(nums[i]);
                if(minHeap.size() > k/2){
                    maxHeap.offer(minHeap.poll());
                }
            }
            while(!minHeap.isEmpty() && !maxHeap.isEmpty() && maxHeap.peek() > minHeap.peek()){
                int temp1 = maxHeap.poll();
                int temp2 = minHeap.poll();
                maxHeap.add(temp2);
                minHeap.add(temp1);
            }
            if(minHeap.size() + maxHeap.size() == k){
                if((k&1)==1){
                    res[i-k+1] = maxHeap.peek();
                }else{
                    res[i-k+1] = ((long)minHeap.peek()+ (long)maxHeap.peek())/2.0;
                }
            }
        }
        return res;
    }
}
/*
    https://leetcode.com/problems/sliding-window-median/
    
    1. SOLUTION 1: Binary Search
    
    The core idea is we maintain a sorted window of elements. Initially we make the 1st window and sort all its elements.
    Then from there onwards any insertion or deletion is done by first finding the appropriate position where the element 
    exists/shoudl exist. This search is done using binary search.
    
    TC: O(klogk (Sorting) + (n - k) * (k + logk)), Binary search in window takes O(logk), but since it is array, insert or delete can take O(k)
    SC: O(k)
    
    2. SOLUTION 2: Height Balanced Tree
    
    Core idea is to use a height balanced tree to save all the elements of window. Since it is a height balanced tree, insertion and deletion takes
    logk. Now we directly want to reach the k/2 th element, then it takes O(k/2). So we need to optimize the mid point fetch.
    
    Initially when the 1st window is built, we find the middle element with O(k/2). Then from there onwards we always adjust the middle position
    by +1 or -1. Since only one element is either added or deleted at a time, so we can move the median left or right based on the situation.
    Eg: [1,2,3,4,5,6,7], median = 4
    
    if we add one element say 9
    [1,2,3,4,5,6,7,9], then check (9 < median): this means 1 extra element on right, don't move and wait to see what happens on deletion
    
    Similarly, now if 2 is deleted, we can just check (2 <= median(4)): this means there will be one less element on left.
    So move median to right by 1. If say an element on right like 7 was deleted, we would have not moved and hence the mid ptr would be 
    at its correct position.
    
    
        (1st window insertion) + remaining_windows * (delete element + add element + get middle)
    TC: O(klogk + (n-k) * (logk + logk + 1)) 
        ~O(klogk + (n-k)*logk) ~O(nlogk)
    SC: O(k)
*/
class Solution {
public:
    ///////////////////// SOLUTION 1: Binary Search
    vector<double> binarySearchSol(vector<int>& nums, int k) {
        vector<double> medians;
        vector<int> window;
        // K is over the size of array
        if(k > nums.size())
            return medians;
        
        int i = 0;
        // add the elements of 1st window
        while(i < k) {
            window.emplace_back(nums[i]);
            ++i;
        }
        
        // sort the window
        sort(window.begin(), window.end());
        // get the median of 1st window
        double median = k % 2 ? window[k / 2] : (double) ((double)window[k/2 - 1] + window[k/2]) / 2;
        medians.emplace_back(median);
        
        for(; i < nums.size(); i++) {
            // search the position of 1st element of the last window using binary search
            auto it = lower_bound(window.begin(), window.end(), nums[i - k]);
            window.erase(it);
            // find the position to insert the new element for the current window
            it = lower_bound(window.begin(), window.end(), nums[i]);
            window.insert(it, nums[i]);
            // Since the window is sorted, we can directly compute the median
            double median = k % 2 ? window[k / 2] : (double) ((double)window[k/2 - 1] + window[k/2]) / 2;
            medians.emplace_back(median);
        }
        return medians;
    }
    
    //////////////////////////// SOLUTION 2: Height Balanced Tree
    vector<double> treeSol(vector<int>& nums, int k) {
        multiset<int> elements;
        vector<double> medians;
        
        int i = 0;
        // process the 1st window
        while(i < k) {
            elements.insert(nums[i]);
            ++i;
        }
        
        // median of 1st window
        auto mid = next(elements.begin(), k / 2);
        double median = k % 2 ? *mid : ((double)*mid + *prev(mid)) / 2;
        medians.emplace_back(median);
        
        for(; i < nums.size(); i++) {
            // insert last element of current window
            elements.insert(nums[i]);
            // If the number lies on the left, left side will have 1 more element.
            // So shift left by 1 pos
            if(nums[i] < *mid)
                --mid;
            
            // remove 1st element of last window
            auto delete_pos = elements.find(nums[i - k]);
            // If the element to be deleted in [first : mid], then right will have extra element
            // so move the mid to right by 1
            // NOTE: We insert the new element and then delete previous element because, if the window has just one element
            // then deleting first will make mid point to invalid position. But inserting first will ensure that there is an 
            // element to point to
            if(nums[i-k] <= *mid)
                ++mid;
            elements.erase(delete_pos);
            
            double median = k % 2 ? *mid : ((double)*mid + *prev(mid)) / 2;
            medians.emplace_back(median);
        }
        
        return medians;
    }
    
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        // return binarySearchSol(nums, k);
        return treeSol(nums, k);
    }
};
function convertNumber(num) {
    return parseFloat(num.toFixed(5))
}
function findMedian(arr) {
    let start = 0;
    let end = arr.length-1;
    let ans;
    if((end-start+1)%2===0) {
        ans = (arr[Math.floor((end+start)/2)] + arr[Math.floor((end+start)/2)+1])/2 ;
    } else {
        ans = arr[Math.floor((end+start)/2)];
    }
    return convertNumber(ans);
}
function updateWinArray(arr) {
    if(arr.length===1) {
        return;
    }
    let ele = arr[arr.length-1];
    let i;
    for(i=arr.length-2;i>=0;i--) {
        if(ele < arr[i]) {
            arr[i+1] = arr[i];
        } else {
            break;
        }
    }
    arr[i+1] = ele;
}
function binarySearch(arr,ele) {
    let start =0, end = arr.length-1, mid;
    while(start<=end) {
        mid = Math.floor((start+end)/2);
        if(arr[mid]===ele) {
            return mid;
        } else if(ele > arr[mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
}
var medianSlidingWindow = function(nums, k) {
    let i=0,j=0,result=[],winArr=[];
    while(j<nums.length) {
        winArr.push(nums[j]);
        updateWinArray(winArr);
        if(j-i+1 < k) {
            j++;
        } else if(j-i+1 === k) {
            let ans = findMedian(winArr);
            result.push(ans);
            let indexOfiEle = binarySearch(winArr,nums[i]);
            winArr.splice(indexOfiEle,1);
            i++;
            j++;
        }
    }
    return result;
};
Sliding Window Median