Skip to content

480. Sliding Window Median 👍

  • Time: $O((n - k + 1)\log k)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    vector<double> ans;
    multiset<double> window(nums.begin(), nums.begin() + k);
    auto it = next(window.begin(), (k - 1) / 2);

    for (int i = k;; ++i) {
      const double median = k % 2 == 0 ? (*it + *next(it)) / 2.0 : *it;
      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;
  }
};