Clean Java with 3 TreeMaps
Sadly, there isn\'t a built-in multiset in Java, therefore we have to play around with treemap. \n\nclass MKAverage {\n    TreeMap<Integer, Integer> top = new T
Sadly, there isn\'t a built-in multiset in Java, therefore we have to play around with treemap. \n```\nclass MKAverage {\n    TreeMap<Integer, Integer> top = new TreeMap<>(), middle = new TreeMap<>(), bottom = new TreeMap<>();\n    Queue<Integer> q = new LinkedList<>();\n    long middleSum;\n    int m, k;\n    int countTop, countBottom;\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n    }\n    \n    public void addElement(int num) {\n        if (q.size() == m) {\n            int pop = q.poll();\n            if (top.containsKey(pop)) { // delete item in top, if present\n                remove(top, pop); \n                countTop--;\n            } else if (middle.containsKey(pop)) { // delete item in bottom, if present\n                remove(middle, pop);\n                middleSum -= pop;\n            } else { // delete item in bottom, if present\n                remove(bottom, pop); \n                countBottom--;\n            }\n        } \n        // insert to middle first\n        add(middle, num);\n        q.offer(num);\n        middleSum += num;\n        // move item from middle to top, to fill k slots\n        while (countTop < k && !middle.isEmpty()) {\n            countTop++;\n            middleSum -= middle.lastKey();\n            add(top, remove(middle, middle.lastKey()));\n        }\n        // rebalance middle and top\n        while (!middle.isEmpty() && !top.isEmpty() && top.firstKey() < middle.lastKey()) {\n            middleSum += top.firstKey();\n            add(middle, remove(top, top.firstKey()));\n            middleSum -= middle.lastKey();\n            add(top, remove(middle, middle.lastKey()));\n        }\n        // move item from middle to bottom, to fill k slots\n        while (countBottom < k && !middle.isEmpty()) {\n            countBottom++;\n            middleSum -= middle.firstKey();\n            add(bottom, remove(middle, middle.firstKey()));\n        }\n        // rebalance middle and bottom\n        while (!middle.isEmpty() && !bottom.isEmpty() && bottom.lastKey() > middle.firstKey()) {\n            middleSum += bottom.lastKey();\n            add(middle, remove(bottom, bottom.lastKey()));\n            middleSum -= middle.firstKey();\n            add(bottom, remove(middle, middle.firstKey()));\n        }\n    }\n    \n    \n    private int remove(TreeMap<Integer, Integer> tm, int num) {\n        tm.put(num, tm.get(num) - 1);\n        if (tm.get(num) == 0) tm.remove(num); \n        return num;\n    }\n    \n    private void add(TreeMap<Integer, Integer> tm, int num) {\n        tm.put(num, tm.getOrDefault(num, 0) + 1);\n    }\n    \n    public int calculateMKAverage() {\n        return q.size() == m ? (int)(middleSum / (m - 2 * k)) : -1;\n    }\n}\n```
[]