Java, Design a class to store sorted nums with duplicates
Intuition\nIf we implement a brute force solution, we will make the following observations:\n1. We need to store only m recent numbers of stream\n2. If the numb
# Intuition\nIf we implement a brute force solution, we will make the following observations:\n1. We need to store only `m` recent numbers of stream\n2. If the numbers will be sorted we in consant time may remove `k` smalles/biggest numbers\n3. We may keep track of `sum` of `[k+1, m-k-2]` sorted numbers\n\nTaking into account the observation above the problem is reduce to the following:\n1. Split `m` numbers into 3 sorted parts of sizes `k`, `m-2*k`, `k`\n2. Add and remove numbers to the collections\n3. Keep the collections balanced\n4. Collections **must** support dupplicate numbers, so we can\'t use `TreeSet`\n\n# Approach\nLet\'s use `TreeMap<val, count>` to solve the problem of duplicate numbers in `TreeSet`. \nLet\'s deisgin a class `SortedList` with required operations and delegate the most work to that class.\n`SortedList` should support the following operations:\n1. add number\n2. remove number\n3. min/max number\n4. size\n5. avg value\n\n# Complexity\n- Time complexity: \n--`max of O(log k) and O(log m-2k)` - add element\n-- `O(1)` - avg\n\n- Space complexity: `O(m)`\n\n# Code\n```\nclass MKAverage {\n    private final int m;\n    private final int k;\n    private final int midSize;\n\n    // keep track queue of size m\n    private final LinkedList<Integer> queue = new LinkedList<>();\n\n    // keep nums sorted in 3 parts: [mins, mids, maxs]\n    private final SortedList mins = new SortedList();\n    private final SortedList mids = new SortedList();\n    private final SortedList maxs = new SortedList();\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n        this.midSize = m - 2*k;\n    }\n\n    // add to sorted collection\n    // remove the oldest element\n    // adjust 3 sorted sub collections [0,k] [k+1, m-k-2] [m-k-1, m-1]\n    public void addElement(int num) {\n        queue.add(num);\n        if (queue.size() > m && queue.peek() == num) { //no rebalance required\n            queue.poll();\n            return;\n        }\n\n        //do rebalance\n        addToSorted(num);\n\n        if (queue.size() > m) {\n            removeFromSorted(queue.poll());\n        }\n    }\n\n    private void removeFromSorted(int toDel) {\n        if (maxs.contains(toDel)) { // maxs has +1 in size\n            maxs.remove(toDel);\n            return;\n        }\n        mids.add(maxs.min());\n        maxs.remove(maxs.min());\n\n        if (mids.contains(toDel)) { // mids has +1 in size\n            mids.remove(toDel);\n            return;\n        }\n        mins.add(mids.min());\n        mids.remove(mids.min());\n\n        // mis has +1 in size\n        mins.remove(toDel);\n    }\n\n    private void addToSorted(int num) {\n        mins.add(num);\n        adjustToSize(mins, mids, k);       // size k       | mins -> mids\n        adjustToSize(mids, maxs, midSize); // size m - 2*k | mids -> maxs\n        //maxs may have k+1 size\n    }\n\n    private void adjustToSize(SortedList low, SortedList big, int size) {\n        if (low.size() > size) {\n            big.add(low.max());\n            low.remove(low.max());\n        }\n    }\n\n    public int calculateMKAverage() {\n        if (queue.size() < m) {\n            return -1;\n        }\n        return mids.avg();\n    }\n\n    private static class SortedList {\n        private TreeMap<Integer, Integer> vals = new TreeMap<>();\n        private int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;\n        private int size;\n        private long totalSum;\n\n        void add(int num) {\n            vals.put(num, vals.getOrDefault(num, 0) + 1);\n            min = Math.min(min, num);\n            max = Math.max(max, num);\n\n            totalSum += num;\n            size++;\n        }\n\n        void remove(int num) {\n            int count = vals.getOrDefault(num, 0);\n            if (count > 0) {\n                size--;\n                totalSum -= num;\n\n                if (count == 1) {\n                    vals.remove(num);\n\n                    if (min == num) {\n                        min = vals.firstKey();\n                    }\n                    if (max == num) {\n                        max = vals.lastKey();\n                    }\n                } else {\n                    vals.put(num, count - 1);\n                }\n            }\n        }\n\n        boolean contains(int num) {\n            return vals.containsKey(num);\n        }\n\n        int avg() {\n            return (int) (totalSum / size);\n        }\n\n        int min() {\n            return min;\n        }\n        int max() {\n            return max;\n        }\n\n        int size() {\n            return size;\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```
['Queue', 'Ordered Map', 'Java']