Clean Solution using three TreeMaps | Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n$$O(log(n))$$ for *addElement*\n$$O(1)$$ for *calculateMKAverage*\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass MKAverage {\n    \n    int m;\n    int k;\n    TreeMap<Integer, Integer> lowBucket;\n    TreeMap<Integer, Integer> midBucket;\n    TreeMap<Integer, Integer> highBucket;\n    int midBucketSum;\n    int lowBucketSize;\n    int highBucketSize;\n\n    Deque<Integer> stream = new ArrayDeque<>();\n\n    public MKAverage(int m, int k) {\n        lowBucket = new TreeMap<>();\n        midBucket = new TreeMap<>();\n        highBucket = new TreeMap<>();\n\n        midBucketSum = 0;\n        lowBucketSize = 0;\n        highBucketSize = 0;\n\n        this.m = m;\n        this.k = k;\n    }\n    \n    public void addElement(int num) {\n        if (lowBucket.isEmpty() || num <= lowBucket.lastKey()) {\n            lowBucket.merge(num, 1, Integer::sum);\n            lowBucketSize++;\n        } else if (highBucket.isEmpty() || num >= highBucket.firstKey()) {\n            highBucket.merge(num, 1, Integer::sum);\n            highBucketSize++;\n        } else {\n            midBucket.merge(num, 1, Integer::sum);\n            midBucketSum += num;\n        }\n\n        stream.offer(num);\n\n        if (stream.size() > m) {\n            int oldestNum = stream.poll();\n\n            if (lowBucket.containsKey(oldestNum)) {\n                if (lowBucket.merge(oldestNum, -1, Integer::sum) == 0) {\n                    lowBucket.remove(oldestNum);\n                }\n                lowBucketSize--;\n            } else if (highBucket.containsKey(oldestNum)) {\n                if (highBucket.merge(oldestNum, -1, Integer::sum) == 0) {\n                    highBucket.remove(oldestNum);\n                }\n                highBucketSize--;\n            } else {\n                if (midBucket.merge(oldestNum, -1, Integer::sum) == 0) {\n                    midBucket.remove(oldestNum);\n                }\n                midBucketSum -= oldestNum;\n            }\n        }\n\n        balanceBucket();\n    }\n    \n    public int calculateMKAverage() {\n        if (stream.size() < m) {\n            return -1;\n        }\n\n        return (int) (midBucketSum / (m - 2 * k));\n    }\n\n    private void balanceBucket() {\n        // Move element from low to middle\n        while (lowBucketSize > k) {\n            int element = lowBucket.lastKey();\n            if (lowBucket.merge(element, -1, Integer::sum) == 0) {\n                lowBucket.remove(element);\n            }\n\n            midBucket.merge(element, 1, Integer::sum);\n            midBucketSum += element;\n\n            lowBucketSize--;\n        }\n\n        // Move element from high to middle\n        while (highBucketSize > k) {\n            int element = highBucket.firstKey();\n            if (highBucket.merge(element, -1, Integer::sum) == 0) {\n                highBucket.remove(element);\n            }\n\n            midBucket.merge(element, 1, Integer::sum);\n            midBucketSum += element;\n\n            highBucketSize--;\n        }\n\n        // Move element from middle to low\n        while (lowBucketSize < k && !midBucket.isEmpty()) {\n            int element = midBucket.firstKey();\n            if (midBucket.merge(element, -1, Integer::sum) == 0) {\n                midBucket.remove(element);\n            }\n            midBucketSum -= element;\n\n            lowBucket.merge(element, 1, Integer::sum);\n            lowBucketSize++;\n        }\n\n        // Move element from middle to high\n        while (highBucketSize < k && !midBucket.isEmpty()) {\n            int element = midBucket.lastKey();\n            if (midBucket.merge(element, -1, Integer::sum) == 0) {\n                midBucket.remove(element);\n            }\n            midBucketSum -= element;\n\n            highBucket.merge(element, 1, Integer::sum);\n            highBucketSize++;\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```
['Java']