Use 3 TreeMap + Queue
Intuition\n1. Tried 3 PQ and each time when calculateMKAverage, traverse small and large PQ to calculate the sum for them == LTE\n2. Tried 3 TreeMap, but did no
# Intuition\n1. Tried 3 PQ and each time when calculateMKAverage, traverse small and large PQ to calculate the sum for them == LTE\n2. Tried 3 TreeMap, but did not use the balance method, rather than, apply moveToSmall, moveToLarge to recursively balance the Map == Stack Overflow\n\n# Approach\nMaintain 3 TreeMap, first one to store the smallest k elements, and the last one to store the largest k elements, the rest are staying in the midBucket. \n\nWhen we need to add a new element, check the window if its size is smaller than m, if it is, directly add it to the potential bucket. If not, remove the earliest element, fetch from queue head, then add it to the potential bucket. \n\nBalance the buckets.\n\n# Complexity\n- Time complexity:\n`O(klogk + mlogm)`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m)\n\n# Code\n```java []\n\n\nclass MKAverage {\n    int m;\n    int k;\n    TreeMap<Integer, Integer> lowBucket;\n    TreeMap<Integer, Integer> midBucket;\n    TreeMap<Integer, Integer> highBucket;\n    long midBucketSum; // prevent overflow\n    long smallSum;\n    long largeSum;\n    int lowBucketSize;\n    int highBucketSize;\n    Deque<Integer> stream;\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n        this.lowBucket = new TreeMap<>();\n        this.midBucket = new TreeMap<>();\n        this.highBucket = new TreeMap<>();\n        this.midBucketSum = 0;\n        this.smallSum = 0;\n        this.largeSum = 0;\n        this.lowBucketSize = 0;\n        this.highBucketSize = 0;\n        this.stream = new ArrayDeque<>(); // Can use linkedlist here\n    }\n\n    public void addElement(int num) {\n        // directly add the element\n        if (lowBucket.isEmpty() || num <= lowBucket.lastKey()) {\n            lowBucket.merge(num, 1, Integer::sum);\n            smallSum += num;\n            lowBucketSize++;\n        } else if (highBucket.isEmpty() || num >= highBucket.firstKey()) {\n            highBucket.merge(num, 1, Integer::sum);\n            largeSum += num;\n            highBucketSize++;\n        } else {\n            midBucket.merge(num, 1, Integer::sum);\n            midBucketSum += num;\n        }\n\n        stream.offer(num);\n        // remove the earliest element added\n        if (stream.size() > m) {\n            int oldestNum = stream.poll();\n            if (lowBucket.containsKey(oldestNum)) {\n                removeElementFromBucket(lowBucket, oldestNum);\n                smallSum -= oldestNum;\n                lowBucketSize--;\n            } else if (highBucket.containsKey(oldestNum)) {\n                removeElementFromBucket(highBucket, oldestNum);\n                largeSum -= oldestNum;\n                highBucketSize--;\n            } else {\n                removeElementFromBucket(midBucket, oldestNum);\n                midBucketSum -= oldestNum;\n            }\n        }\n        // most important step, balance the tree.\n        balanceBuckets();\n    }\n\n    public int calculateMKAverage() {\n        if (stream.size() < m) {\n            return -1;\n        }\n        return (int) (midBucketSum / (m - 2 * k));\n    }\n\n    private void balanceBuckets() {\n        // Prevent to recursively move the elements, it will cause Stack Overflow.\n        while (lowBucketSize > k) {\n            int largestInLow = lowBucket.lastKey();\n            removeElementFromBucket(lowBucket, largestInLow);\n            smallSum -= largestInLow;\n            lowBucketSize--;\n\n            midBucket.merge(largestInLow, 1, Integer::sum);\n            midBucketSum += largestInLow;\n        }\n\n        while (highBucketSize > k) {\n            int smallestInHigh = highBucket.firstKey();\n            removeElementFromBucket(highBucket, smallestInHigh);\n            largeSum -= smallestInHigh;\n            highBucketSize--;\n\n            midBucket.merge(smallestInHigh, 1, Integer::sum);\n            midBucketSum += smallestInHigh;\n        }\n\n        while (lowBucketSize < k && !midBucket.isEmpty()) {\n            int smallestInMid = midBucket.firstKey();\n            removeElementFromBucket(midBucket, smallestInMid);\n            midBucketSum -= smallestInMid;\n\n            lowBucket.merge(smallestInMid, 1, Integer::sum);\n            smallSum += smallestInMid;\n            lowBucketSize++;\n        }\n\n        while (highBucketSize < k && !midBucket.isEmpty()) {\n            int largestInMid = midBucket.lastKey();\n            removeElementFromBucket(midBucket, largestInMid);\n            midBucketSum -= largestInMid;\n\n            highBucket.merge(largestInMid, 1, Integer::sum);\n            largeSum += largestInMid;\n            highBucketSize++;\n        }\n    }\n\n    private void removeElementFromBucket(TreeMap<Integer, Integer> bucket, int num) {\n        bucket.put(num, bucket.get(num) - 1);\n        if (bucket.get(num) == 0) {\n            bucket.remove(num);\n        }\n    }\n}\n\n```
['Java']