The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window.

**arr** = 1, 3, 5, 10, 6, 9, 2

**k** = 3

would yield a result of 3, 5, 6, 9, 6

Using std::priority_queue (in C++) for the heap implementation, there’s a minHeap and maxHeap. In a single iteration, insert the value entering our window in the correct heap, rebalance as necessary, add the median to the result (if the window is big enough), then remove the value which is leaving the window from whatever heap it’s in: This could require moving all but 1 heap element to the other heap, then moving them back.

The lesson I saw this on actually inherits from priority queue and implements remove functionality: Linear search [O(k)], then removes the item [O(log k)]. It claims O(n * k) complexity as at each iteration the insertion is O(log k) and the search to remove is O(k). I assume in an interview extending a heap beyond it’s traditional form is not only unnecessary but probably frowned upon.

I’m curious of the complexity at which the version w/o the direct removal would run. The O(n) part is obvious but the sub operations not as clear to me. A heap will generally have k/2 items in it. In the worst case you delete [O(log k)] and then insert [O(1)] each one. My mind is telling me O(n * k log k) but I wouldn’t bet my house on it.

For the record: Not looking for an optimal solution – just the runtime of this one.

`class SlidingWindowMedian { public: virtual std::vector<double> findSlidingWindowMedian(const std::vector<int> &nums, int k) { std::vector<double> result{}; int left{0}; for (int right = 0; right < nums.size(); right++) { insert(nums[right]); if (right >= k-1) { result.push_back(getMedian()); remove(nums[left++]); } } return result; } void insert(int num) { if (maxHeap.empty() || maxHeap.top() >= num) { maxHeap.push(num); } else { minHeap.push(num); } if (maxHeap.size() > minHeap.size() + 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } else if (minHeap.size() > maxHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } } double getMedian() { if (maxHeap.size() == minHeap.size()) { return (maxHeap.top() + minHeap.top()) / 2.0; } else if (maxHeap.size() > minHeap.size()) { return maxHeap.top(); } else { return minHeap.top(); } } // Faster would be to extend priority queue to support remove void remove(int num) { if (maxHeap.top() >= num) { while (maxHeap.top() != num) { minHeap.push(maxHeap.top()); maxHeap.pop(); } if (maxHeap.top() == num) maxHeap.pop(); while (minHeap.size() > maxHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } } else { while (!minHeap.empty() && minHeap.top() != num) { maxHeap.push(minHeap.top()); minHeap.pop(); } if (minHeap.top() == num) minHeap.pop(); while(maxHeap.size() > minHeap.size() + 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } } } std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap{}; std::priority_queue<int, std::vector<int>, std::less<int>> maxHeap{}; }; `