My Intuitive C++ Solution, to solve most of streaming data Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nIf you have solved other streaming data related problem. You can build this solution ba
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf you have solved other streaming data related problem. You can build this solution based on the solution of other similar problems. One such problem is median in a streaming data. \n\n# Approach\nFor this you have to keep in mind few things : \n\n1. Queue maintaining order of inputs, so that when the size of queue is m, you can easily remove the stale value.\n2. Maintain three multiset to track the lowest K, top K and mid elements.\n3. Balance the sizes of each multiset at every insertion.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(log(m))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass MKAverage {\n    int total;\n    int m;\n    int k;\n    queue<int> recentData;\n    multiset<int, greater<int>> smallestK;\n    multiset<int> greatestK;\n    multiset<int> midElements;\n    long midSum;\npublic:\n    MKAverage(int m, int k) {\n        total = 0;\n        this->m = m;\n        this->k = k;\n        midSum = 0;\n    }\n\n    //   1. < k elements;\n    //   2. > k & < 2k elements;\n    //   3. > 2k & < m elements;\n    //   4. > m elements;\n    void addElement(int num) {\n        // If we have already m data in queue then remove the stale data\n        if(total == m) {\n            int stale = recentData.front();\n\n            recentData.pop();\n            recentData.push(num);\n\n            // Remove the stale value from the appropriate set containing the value\n            if(greatestK.find(stale) != greatestK.end()) {\n                greatestK.erase(greatestK.find(stale));\n            }\n            else if(smallestK.find(stale) != smallestK.end()) {\n                smallestK.erase(smallestK.find(stale));\n            }\n            else {\n                // If the value in middle set, update midSum\n                midElements.erase(midElements.find(stale));\n                midSum -= stale;\n            }\n            total--;\n        }\n        else {\n            recentData.push(num);\n        }\n\n\n        if(total < k) {\n            greatestK.insert(num);\n        }\n        else if(total < 2*k) {\n            greatestK.insert(num);\n            int smaller = *greatestK.begin();\n            smallestK.insert(smaller);\n            greatestK.erase(greatestK.begin());\n        }\n        else if(total < m) {\n            // Insert from Greater to Smaller\n            greatestK.insert(num);\n            int smaller = *greatestK.begin();\n            greatestK.erase(greatestK.begin());\n            midElements.insert(smaller);\n\n            // Add smaller value of top k to midSum\n            midSum += smaller;\n            smaller = *midElements.begin();\n            midElements.erase(midElements.begin());\n            // Remove the smaller value of mid elements to midSum\n            midSum -= smaller;\n            smallestK.insert(smaller);\n\n            // Now Balance the size\n            if(smallestK.size() > k) {\n                int greater = *smallestK.begin();\n                smallestK.erase(smallestK.begin());\n\n                midElements.insert(greater);\n                midSum += greater;\n\n                if(midElements.size() > m - 2*k) {\n                    auto ptr = midElements.end();\n                    greater = *(--ptr);\n                    midElements.erase(ptr);\n                    midSum -= greater;\n                    greatestK.insert(greater);\n                }\n            }\n        }\n\n        total++;\n    }\n    \n    int calculateMKAverage() {\n        if(total < m) {\n            return -1;\n        }\n        else {\n            return midSum/(m-2*k);\n        }\n    }\n};\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * MKAverage* obj = new MKAverage(m, k);\n * obj->addElement(num);\n * int param_2 = obj->calculateMKAverage();\n */\n```
['Queue', 'Heap (Priority Queue)', 'Data Stream', 'Ordered Set', 'C++']