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

#include <queue>
#include <vector>
#include <unordered_map> // already functions like a defaultdict

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        /*
        - two heap approach
        - assume that min is allowed to have one more than max
        - median is in min if min is bigger, otherwise average of the tops of the heaps
        - lazy removal, when an element leaves our window make note
        - if a removed element ever shows up at the top of a heap, pop that element
        - if k is odd, the min heap has one more element
        */
        std::priority_queue<double> min_heap; // large half of values, multiply by -1
        std::priority_queue<double> max_heap; // small half of values, allowed to have one more value
        std::unordered_map<int,int> to_remove; // key: number to remove, value: counter
        std::vector<double> result;

        // populate the two heaps for the first window
        for (int i = 0; i < k; ++i) {
            // push to max heap by defualt and swap over to min heap
            max_heap.push(double(nums[i]));
            double swap = max_heap.top();
            max_heap.pop();
            min_heap.push(-1 * swap);

            // make sure the min heap is not bigger
            if(min_heap.size() > max_heap.size()) {
                double swap = min_heap.top() * -1;
                min_heap.pop();
                max_heap.push(swap);
            }
        }

        // get the median for the first window
        // if the window is odd the median is on the max_heap
        double median;
        if (k % 2 == 1) {
            median = max_heap.top();
            result.push_back(median);
        }
        else {
            median = (max_heap.top() + (-1 * min_heap.top())) / 2.0;
            result.push_back(median);
        }

        // slide the window, getting the median and removing values when necessary
        for (int i = k; i < nums.size(); ++i) {
            // record the number leaving the window
            auto remove = nums[i-k];
            ++to_remove[remove];

            // how does removal impact heap size?
            int balance;
            if (remove <= median) {
                balance = -1; // removed from max_heap, one less value in max heap
            }
            else {
                balance = 1; // removed from min_heap, one extra value in max heap
            }

            // insert the next number according to its relationship to the median
            if (nums[i] <= median) {
                ++balance;
                max_heap.push(double(nums[i]));
            }
            else{
                --balance;
                min_heap.push(-1 * double(nums[i]));
            }

            // swap if necessary
            if (balance < 0) { // need to add to the max heap to rebalance
                max_heap.push(-1 * min_heap.top());
                min_heap.pop();
            }
            else if (balance > 0) { // max heap has too many elements
                min_heap.push(-1 * max_heap.top());
                max_heap.pop();
            }

            // remove values only if they are at the top of either respective heap
            while (!max_heap.empty() && to_remove[max_heap.top()] > 0) { // pop if the top of the max_heap is outside the window
                --to_remove[max_heap.top()];
                max_heap.pop();
            }
            while (!min_heap.empty() && to_remove[-1 * min_heap.top()] > 0) { // pop if the top of the min_heap is outside the window
                --to_remove[-1 * min_heap.top()];
                min_heap.pop();
            }

            // get the median of this window
            if (k % 2 == 1) {
                median = max_heap.top();
                result.push_back(median);
            }
            else {
                median = (max_heap.top() + (-1 * min_heap.top())) / 2.0;
                result.push_back(median);
            }
        }

        return result;
    }
};
41290