Easy to Understand 3 Multisets Approach
Approach:\nIn this problem we will be using SlidingWindow and Multiset so solve this problem.\nFor SlidingWindow we are using a queue stream and 3 Multisets kBo
### Approach:\nIn this problem we will be using **SlidingWindow** and **Multiset** so solve this problem.\nFor **SlidingWindow** we are using a `queue` `stream` and 3 **Multisets** `kBottom`, `middle` and `kTop` track the three buckets:\n\n**We will divide the 3 bucket as:**\n1. Bottom `K` numbers, MIDDLE numbers `(M - 2 * K)`, top `K` numbers\n\t`// also tracking numbers come in and leave.`\n     `// also tracking the sum of the MIDDLE bucket.`\n2. At some point of time, all the buckets will all be satistified our first requirement and we need to add a new number.\n\ti) i.e. `K` bottom numbers, `MIDDLE` numbers, `K` top numbers -> a new number come in\n\tii) Then we need to remove a number because of the sliding window moves\n\tiii) When a number is being removed, the we have to maintain the three buckets like this way \n\tiv) i.e. to be `K` numbers, `MIDDLE` numbers, `K-1` numbers. \n\tv) First we will remove from the last bucket then middle and very last from the first bucket.\n     \n3. After that, we will add the new elemment into the bottom bucket. So it becomes `K+1` numbers, MIDDLE numbers,` K-1` numbers.     \n4. We remove the biggest value from the botton bucket and add it to the MIDDLE bucket. So it becomes `K` nums, `MIDDLE+1` nums, `K-1` nums.\n5. We then remove the biggest value from the `MIDDLE` bucket and add it to the top bucket\n6.  So again, the three buckets become as approach described.\n\n**Time and Space Complexity:**\n\nTime Complexity: \nAdding and removing from a `queue` is constant `O(1)` time complexity and Inserting, erasing, and finding from `multiset` is `O(log n)`.  \nso `addElement()` will be `O(log m)` and `calculateMKAverage()` will be `O(1)`\n\nSpace Complexity:\nAt most `m` elements will be present so space complexity will be `O(m)`.\n\n```\nenum class Positions {\n    kBottom = 0,\n    kMiddle,\n    kTop,\n};\n\nclass MKAverage {\nprivate:\n    int m, k;\n    long long sum;\n    \n    queue<int> stream;\n    multiset<int> kBottom;\n    multiset<int> middle;\n    multiset<int> kTop;\npublic:\n    MKAverage(int m, int k) {\n        this->m = m, this->k = k;\n        sum = 0;\n    }\n    \n    void addElement(int num) {\n        stream.push(num);\n        \n        if (stream.size() > m) {\n            int removedValue = stream.front();\n            stream.pop();\n            if (kTop.find(removedValue) != kTop.end()) {\n                removingValue(removedValue, Positions::kTop);\n            } else if (middle.find(removedValue) != middle.end()) {\n                removingValue(removedValue, Positions::kMiddle);\n                int value = removeSmallest(kTop);\n                addingValue(value, Positions::kMiddle);\n            } else {\n                removingValue(removedValue, Positions::kBottom);\n                int value = removeSmallest(kTop);\n                addingValue(value, Positions::kMiddle);\n                \n                value = removeSmallest(middle);\n                sum -= value; // Already removed the value so don\'t calling the removingValue function, just decrement the value from sum\n                addingValue(value, Positions::kBottom);\n            }\n        }\n        \n        add(num);\n    }\n    \n    int calculateMKAverage() {\n        if (stream.size() < m) {\n            return -1;\n        }\n        return sum / (int)middle.size();\n    }\nprivate:\n    void add(int num) {\n        addingValue(num, Positions::kBottom);\n        if (kBottom.size() > k) {\n            int value = removeLargest(kBottom);\n            addingValue(value, Positions::kMiddle);\n            if (middle.size() > m - 2 * k) {\n                value = removeLargest(middle);\n                sum -= value; // For middle as we have already deleted the value from the set, so we are not calling the removingValue function\n                addingValue(value, Positions::kTop);\n            }\n        }\n    }\n    void addingValue(int value, enum Positions pos) {\n        switch (pos) {\n            case Positions::kBottom:\n                kBottom.insert(value);\n                break;\n            case Positions::kMiddle:\n                middle.insert(value);\n                sum += value;\n                break;\n            case Positions::kTop:\n                kTop.insert(value);\n                break;\n        }\n    }\n    void removingValue(int value, enum Positions pos) {\n        switch (pos) {\n            case Positions::kBottom:\n                kBottom.erase(kBottom.find(value));\n                break;\n            case Positions::kMiddle:\n                middle.erase(middle.find(value));\n                sum -= value;\n                break;\n            case Positions::kTop:\n                kTop.erase(kTop.find(value));\n                break;\n        }\n    }\n    int removeSmallest(multiset<int>& set) {\n        auto smallest = set.begin();\n        int result = *smallest;\n        set.erase(smallest);\n        return result;\n    }\n    int removeLargest(multiset<int>& set) {\n        auto largest = --set.end();\n        int result = *largest;\n        set.erase(largest);\n        return result;\n    }\n};\n ```
['Queue', 'C', 'C++']