LeetCode Solutions

480. Sliding Window Median

Time: $O((n - k + 1)\log k)$

Space: $O(k)$

			

class Solution {
 public:
  vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    vector<double> ans;
    multiset<double> window(begin(nums), begin(nums) + k);
    auto it = next(begin(window), (k - 1) / 2);

    for (int i = k;; ++i) {
      const double median = k & 1 ? *it : (*it + *next(it)) / 2.0;
      ans.push_back(median);
      if (i == nums.size())
        break;
      window.insert(nums[i]);
      if (nums[i] < *it)
        --it;
      if (nums[i - k] <= *it)
        ++it;
      window.erase(window.lower_bound(nums[i - k]));
    }

    return ans;
  }
};