Java O(logN), O(1) time. beat 100%. SortedList implementation.
Java doesn\'t has SortedList like python. So manually implemented one.\nThe idea is to maintain 3 SortedList. Every time when add new element, remove old elemen
Java doesn\'t has ```SortedList``` like python. So manually implemented one.\nThe idea is to maintain 3 SortedList. Every time when add new element, remove old element, keep 3 ```SortedList``` size as required.\nTotal size of ```l1```, ```l2```, ```l3``` is ```m```, ```l1```, ```l3``` has length of ```k```\n```\npublic class MKAverage {\n\n    int m, k;\n    Deque<Integer> queue = new ArrayDeque();\n    SortedList l1 = new SortedList();\n    SortedList l2 = new SortedList();\n    SortedList l3 = new SortedList();\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n    }\n\n    public void addElement(int num) {\n        queue.addLast(num);\n        // add in the proper place\n        if (l1.isEmpty() || num <= l1.getLast()) {\n            l1.add(num);\n        } else if (l2.isEmpty() || num <= l2.getLast()) {\n            l2.add(num);\n        } else {\n            l3.add(num);\n        }\n        if (queue.size() > m) {\n            int removedElement = queue.removeFirst();\n            // remove in the proper place\n            if (l1.contains(removedElement)) {\n                l1.remove(removedElement);\n            } else if (l2.contains(removedElement)) {\n                l2.remove(removedElement);\n            } else {\n                l3.remove(removedElement);\n            }\n        }\n\t\t// adjust size of l1, l2, l3\n        if (l1.size > k) {\n            l2.add(l1.removeLast());\n        } else if (l1.size < k && !l2.isEmpty()) {\n            l1.add(l2.removeFirst());\n        }\n        if (l2.size > m - k - k) {\n            l3.add(l2.removeLast());\n        } else if (l2.size < m - k - k && !l3.isEmpty()) {\n            l2.add(l3.removeFirst());\n        }\n    }\n\n    public int calculateMKAverage() {\n        if (l1.size + l2.size + l3.size < m) {\n            return -1;\n        }\n        return (int)Math.floor((double)(l2.sum) / (l2.size));\n    }\n\n    static class SortedList {\n        long sum;\n        int size;\n        TreeMap<Integer, Integer> tm = new TreeMap<>();\n\n        public void add(int n) {\n            tm.put(n, tm.getOrDefault(n, 0) + 1);\n            sum += n;\n            size++;\n        }\n\n        public boolean isEmpty() {\n            return size == 0;\n        }\n\n        public boolean contains(int n) {\n            return tm.containsKey(n);\n        }\n\n        public void remove(int n) {\n            if (!tm.containsKey(n)) {\n                return;\n            }\n            int count = tm.get(n);\n            sum -= n;\n            size--;\n            if (count == 1) {\n                tm.remove(n);\n            } else {\n                tm.put(n, count - 1);\n            }\n        }\n\n        public int removeLast() {\n            Map.Entry<Integer, Integer> lastEntry = tm.lastEntry();\n            if (lastEntry.getValue() == 1) {\n                tm.remove(lastEntry.getKey());\n            } else {\n                tm.put(lastEntry.getKey(), lastEntry.getValue() - 1);\n            }\n            sum -= lastEntry.getKey();\n            size--;\n            return lastEntry.getKey();\n        }\n\n        public int removeFirst() {\n            Map.Entry<Integer, Integer> firstEntry = tm.firstEntry();\n            if (firstEntry.getValue() == 1) {\n                tm.remove(firstEntry.getKey());\n            } else {\n                tm.put(firstEntry.getKey(), firstEntry.getValue() - 1);\n            }\n            sum -= firstEntry.getKey();\n            size--;\n            return firstEntry.getKey();\n        }\n\n        public int getLast() {\n            return tm.lastKey();\n        }\n\n        public int getFirst() {\n            return tm.firstKey();\n        }\n    }\n\t\n}\n```
[]