<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 {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        //vector to store median        
        vector<double> median;
        //map to delete the elements that are to be removed from sliding window 
        unordered_map<int,int> mp;
        //to store the element in heap in descending order
        priority_queue<int> maxHeap;
        //to store the element in heap in ascending order
        priority_queue<int, vector<int>, greater<int>> minHeap;

        //first insert the element upto the size of window in maxHeap
        for(int i=0;i<k;i++)
        {
            maxHeap.push(nums[i]);
        }

        //Now to balance the size of maxHeap and minHeap, insert half elements in minHeap
        for(int i=0; i<k/2; i++)
        {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }

        //for rest of the elements
        for(int i=k; i<nums.size(); i++)
        {

            if(k%2 != 0) //if k is odd
                median.push_back(maxHeap.top()*1.0);
            else  // if k is even
                median.push_back((maxHeap.top()*1.0 + minHeap.top()*1.0)/2);

            //to remove previous element from sliding window and inserting new element and checking the balance of maxHeap and minHeap
            int p = nums[i-k], q = nums[i], balance = 0;

            //if p is present in maxHeap
            if(p <= maxHeap.top())
            {
                balance--;
                if(p == maxHeap.top())
                {
                    maxHeap.pop();
                }
                else
                {
                    mp[p]++;
                }
            }
            else  //if p is present in minHeap
            {
                balance++;
                if(p == minHeap.top())
                {
                    minHeap.pop();
                }
                else
                {
                    mp[p]++;
                }
            }

            //to insert q in maxHeap when q is smaller than top of the maxHeap
            if(!maxHeap.empty() && q<=maxHeap.top())
            {
                maxHeap.push(q);
                balance++;
            }
            else  //if q is greater the top of maxHeap then insert it into minHeap
            {
                minHeap.push(q);
                balance--;
            }
            
            //if balance > 0
            if(balance > 0)
            {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            }   //if balance < 0
            else if(balance < 0)
            {
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }

            while(!maxHeap.empty() && mp[maxHeap.top()])
            {
                mp[maxHeap.top()]--;
                maxHeap.pop();
            }
            while(!minHeap.empty() && mp[minHeap.top()])
            {
                mp[minHeap.top()]--;
                minHeap.pop();
            }
        }
        if(k%2 != 0)
            median.push_back(maxHeap.top()*1.0);
        else 
            median.push_back((maxHeap.top()*1.0 + minHeap.top()*1.0)/2);
        return median;
    }
};
39770