Multiset | Java | O(NlogM) time | O(M) space
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nUsed three MultiSet to track the state of the elements added.\nsmallest -
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nUsed three MultiSet to track the state of the elements added.\nsmallest - tracks the smallest k elemtns in the current window\nlargest - tracks the smallest k elemtns in the current window\nothers - tracks the rest of the elements\n\nUsed a FIFO queue to track the order of elements added.\n\nAlgorithm:\n**addElement**\n1) Remove the element not in the m-window if necessary from the multi-sets\n2) Add element to the fifo queue\n3) Add element to the state (multi-sets)\n\n# Complexity\n- Time complexity:\naddElement: O(log(m))\ncalculateMKAverage: O(1)\n\n- Space complexity:\nO(m)\n\n# Code\n```\nclass MKAverage {\n    MultiSet smallest = new MultiSet();\n    MultiSet largest = new MultiSet();\n    MultiSet others = new MultiSet();\n\n    Queue<Integer> queue = new LinkedList<>();\n\n    final int m;\n    final int k;\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.offer(num);\n\n        // remove\n        if (queue.size() > m) {\n            if (queue.peek() < others.getFirst()) {\n                smallest.remove(queue.poll());\n            } else if (queue.peek() > others.getLast()) {\n                largest.remove(queue.poll());\n            } else {\n                others.remove(queue.poll());\n            }\n        }\n\n        others.add(num);\n\n        if (smallest.size() < k || smallest.getLast() > others.getFirst()) {\n            smallest.add(others.pollFirst());\n            if (smallest.size() > k) {\n                others.add(smallest.pollLast());\n            }\n        }\n\n        if (others.isEmpty()) {\n            return;\n        }\n\n        if (largest.size() < k || largest.getFirst() < others.getLast()) {\n            largest.add(others.pollLast());\n            if (largest.size() > k) {\n                others.add(largest.pollFirst());\n            }\n        }\n    }\n    \n    public int calculateMKAverage() {\n        if (queue.size() < m) {\n            return -1;\n        }\n        return others.avg();\n    }\n}\n\nclass MultiSet {\n    TreeMap<Integer, Integer> elements = new TreeMap<>();\n    int size = 0;\n    long total = 0L;\n\n    void add(int num) {\n        elements.put(num, elements.getOrDefault(num, 0) + 1);\n        size++;\n        total += num;\n    }\n\n    int pollFirst() {\n        int k = elements.firstKey();\n        remove(k);\n        return k;\n    }\n\n    int pollLast() {\n        int k = elements.lastKey();\n        remove(k);\n        return k;\n    }\n\n    int getFirst() {\n        return elements.firstKey();\n    }\n\n    int getLast() {\n        return elements.lastKey();\n    }\n\n    int size() {\n        return size;\n    }\n\n    boolean isEmpty() {\n        return elements.isEmpty();\n    }\n\n    void remove(int num) {\n        // assumption: the key is present\n        int v = elements.get(num) - 1;\n        if (v == 0) {\n            elements.remove(num);\n        } else {\n            elements.put(num, elements.get(num) - 1);\n        }\n        size--;\n        total -= num;\n    }\n\n    int avg() {\n        return (int) (total / size);\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']