Java O(1) Calcualte, O(log(m)) add. Three MultiSet
Should be short if Java has a native MultiSet implement as Guava TreeMultiSet\n\nclass MKAverage {\n    private MultiTreeSet bottom = new MultiTreeSet();\n    p
Should be short if Java has a native MultiSet implement as [Guava TreeMultiSet](https://guava.dev/releases/21.0/api/docs/com/google/common/collect/TreeMultiset.html)\n```\nclass MKAverage {\n    private MultiTreeSet bottom = new MultiTreeSet();\n    private MultiTreeSet middle = new MultiTreeSet();\n    private MultiTreeSet top = new MultiTreeSet();    \n    private int m, k;\n    private LinkedList<Integer> elements = new LinkedList<>();\n    private long sum = 0;\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n    }\n    \n    public void addElement(int num) {\n        elements.add(num);\n        bottom.add(num); // blindly add to bottom\n\t\t// remove the element from the corresponding stack\n        if (elements.size() > m) {\n            int removed = elements.removeFirst();\n            if (bottom.contains(removed)) {\n                bottom.remove(removed);\n            } else if (middle.contains(removed)) {\n                middle.remove(removed);\n                sum -= removed;\n            } else if (top.contains(removed)) {\n                top.remove(removed);\n            }\n        }\n        if (elements.size() == m) {\n\t\t    // once we reach m, bottom can only be >= k (because each call, we add 1 element to bottom, and remove at most 1 element from it)\n            while (bottom.total > k) {\n                int element = bottom.pollLast();\n                middle.add(element);\n                sum += element;\n            }\n\t\t\t// fix size of middle stack\n            while (middle.total > m - 2*k) {\n                int element = middle.pollLast();\n                top.add(element);\n                sum -= element;\n            }\n            // fix ordering of bottom-middle stack\n            while (bottom.getLast() > middle.getFirst()) {\n                int e1 = middle.pollFirst();\n                int e2 = bottom.pollLast();\n                middle.add(e2);\n                bottom.add(e1);\n                sum = sum - e1 + e2;\n            }\n            // fix ordering of middle-top stack\n            while (middle.getLast() > top.getFirst()) {\n                int e1 = top.pollFirst();\n                int e2 = middle.pollLast();\n                middle.add(e1);\n                top.add(e2);\n                sum = sum + e1 - e2;\n            }\n        }\n    }\n    \n    public int calculateMKAverage() {\n        return elements.size() == m ? (int)(sum/(m - 2*k)) : -1;\n    }\n    \n    static class MultiTreeSet {\n        private TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();\n        private int total = 0;\n        \n        public void add(int val) {\n            int count = map.getOrDefault(val, 0) + 1;\n            map.put(val, count);\n            total++;\n        }\n        \n        public void remove(int val) {\n            int count = map.get(val);\n            if (count == 1) map.remove(val);\n            else map.put(val, count-1);\n            total--;\n        }\n        \n        public boolean contains(int val) {\n            return map.containsKey(val);\n        }\n        \n        public int getFirst() {\n            return map.firstKey();\n        }\n        \n        public int getLast() {\n            return map.lastKey();\n        }\n        \n        public int pollFirst() {\n            int first = map.firstKey();\n            remove(first);\n            return first;\n        }\n        \n        public int pollLast() {\n            int last = map.lastKey();\n            remove(last);\n            return last;\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```
[]