1
/*
2
    https://leetcode.com/problems/sliding-window-median/
3

4
    1. SOLUTION 1: Binary Search
5

6
    The core idea is we maintain a sorted window of elements. Initially we make
7
   the 1st window and sort all its elements. Then from there onwards any
8
   insertion or deletion is done by first finding the appropriate position where
9
   the element exists/shoudl exist. This search is done using binary search.
10

11
    TC: O(klogk (Sorting) + (n - k) * (k + logk)), Binary search in window takes
12
   O(logk), but since it is array, insert or delete can take O(k) SC: O(k)
13

14
    2. SOLUTION 2: Height Balanced Tree
15

16
    Core idea is to use a height balanced tree to save all the elements of
17
   window. Since it is a height balanced tree, insertion and deletion takes
18
    logk. Now we directly want to reach the k/2 th element, then it takes
19
   O(k/2). So we need to optimize the mid point fetch.
20

21
    Initially when the 1st window is built, we find the middle element with
22
   O(k/2). Then from there onwards we always adjust the middle position by +1 or
23
   -1. Since only one element is either added or deleted at a time, so we can
24
   move the median left or right based on the situation. Eg: [1,2,3,4,5,6,7],
25
   median = 4
26

27
    if we add one element say 9
28
    [1,2,3,4,5,6,7,9], then check (9 < median): this means 1 extra element on
29
   right, don't move and wait to see what happens on deletion
30

31
    Similarly, now if 2 is deleted, we can just check (2 <= median(4)): this
32
   means there will be one less element on left. So move median to right by 1.
33
   If say an element on right like 7 was deleted, we would have not moved and
34
   hence the mid ptr would be at its correct position.
35

36

37
        (1st window insertion) + remaining_windows * (delete element + add
38
   element + get middle) TC: O(klogk + (n-k) * (logk + logk + 1)) ~O(klogk +
39
   (n-k)*logk) ~O(nlogk) SC: O(k)
40
*/
41
class Solution {
42
 public:
43
  ///////////////////// SOLUTION 1: Binary Search
44
  vector<double> binarySearchSol(vector<int> &nums, int k) {
45
    vector<double> medians;
46
    vector<int> window;
47
    // K is over the size of array
48
    if (k > nums.size()) return medians;
49

50
    int i = 0;
51
    // add the elements of 1st window
52
    while (i < k) {
53
      window.emplace_back(nums[i]);
54
      ++i;
55
    }
56

57
    // sort the window
58
    sort(window.begin(), window.end());
59
    // get the median of 1st window
60
    double median = k % 2 ? window[k / 2] : (double)((double)window[k / 2 - 1] + window[k / 2]) / 2;
61
    medians.emplace_back(median);
62

63
    for (; i < nums.size(); i++) {
64
      // search the position of 1st element of the last window using binary
65
      // search
66
      auto it = lower_bound(window.begin(), window.end(), nums[i - k]);
67
      window.erase(it);
68
      // find the position to insert the new element for the current window
69
      it = lower_bound(window.begin(), window.end(), nums[i]);
70
      window.insert(it, nums[i]);
71
      // Since the window is sorted, we can directly compute the median
72
      double median =
73
          k % 2 ? window[k / 2] : (double)((double)window[k / 2 - 1] + window[k / 2]) / 2;
74
      medians.emplace_back(median);
75
    }
76
    return medians;
77
  }
78

79
  //////////////////////////// SOLUTION 2: Height Balanced Tree
80
  vector<double> treeSol(vector<int> &nums, int k) {
81
    multiset<int> elements;
82
    vector<double> medians;
83

84
    int i = 0;
85
    // process the 1st window
86
    while (i < k) {
87
      elements.insert(nums[i]);
88
      ++i;
89
    }
90

91
    // median of 1st window
92
    auto mid = next(elements.begin(), k / 2);
93
    double median = k % 2 ? *mid : ((double)*mid + *prev(mid)) / 2;
94
    medians.emplace_back(median);
95

96
    for (; i < nums.size(); i++) {
97
      // insert last element of current window
98
      elements.insert(nums[i]);
99
      // If the number lies on the left, left side will have 1 more element.
100
      // So shift left by 1 pos
101
      if (nums[i] < *mid) --mid;
102

103
      // remove 1st element of last window
104
      auto delete_pos = elements.find(nums[i - k]);
105
      // If the element to be deleted in [first : mid], then right will have
106
      // extra element so move the mid to right by 1 NOTE: We insert the new
107
      // element and then delete previous element because, if the window has
108
      // just one element then deleting first will make mid point to invalid
109
      // position. But inserting first will ensure that there is an element to
110
      // point to
111
      if (nums[i - k] <= *mid) ++mid;
112
      elements.erase(delete_pos);
113

114
      double median = k % 2 ? *mid : ((double)*mid + *prev(mid)) / 2;
115
      medians.emplace_back(median);
116
    }
117

118
    return medians;
119
  }
120

121
  vector<double> medianSlidingWindow(vector<int> &nums, int k) {
122
    // return binarySearchSol(nums, k);
123
    return treeSol(nums, k);
124
  }
125
};