Java | Queue + TreeMap | Explained, Example
Haven\'t seen this in the comments so I\'ll just go ahead with some bullet points.\n\n We need to be able to access the first and last k elements (of the last m
Haven\'t seen this in the comments so I\'ll just go ahead with some bullet points.\n\n* We need to be able to access the first and last k elements (of the last m elements) of the stream. If there was something as a SortedQueue in Java it would be cool, but there isn\'t, so **TreeMap** was all I could come up with, in order to manage the repeated elements correctly. This TreeMap will preserve the natural order of the last m elements of the stream.\n\n\n* We\'re gonna keep track of the **totalSum** of the last m elements of the stream.\n\n* We need to keep the last m elements of the Stream. We\'ll use a **queue** to do this. As soon as the queue has more than m elements, we push the first one out and subtract it from the total sum. We also reduce its count from the TreeMap (and delete the key if its count becomes 0).\n\n\n* In order to subtract the first and last k elements, we literally just have to get that info from the TreeMap. In a SortedList, we would do an iteration for the first k and one for the last k, subtract the sum of those from the totalSum. Here we have to be more careful with how we advance through the keys, since they\'re grouped by counts.\n\n* Next, just take the average, which is **(totalSum - sumOfExtremes) / (m - 2 * k)**\n\nExample:\n\n```\nM = 5, K = 2\nStream:\n[17612, 74607, 8272, 33433, 8272, 64938, [Takes average], 99741]\n\nObserve, when the average is taken, our q is like\nQ = [ 8272, 33433, 8272, 64938, 99741 ]\n\nOur Tree Map is (, in order):\n[ 8272 --> 2, 33433 -> 1, 64938 --> 1, 99741 --> 1 ]\n\nGetting the sum of\n* The first two elements: 8272 + 8272 = 16544\n* The last two elements: 64938 + 99741 = 164679\n\nFinally getting the average:\n\n(totalSum - sumOfExtremes) / (m - 2*k) = (214656 - 181223) / (5 - 2 * 2) = 33433 / 1 = 33433\n```\n\n\nThis is not the fastest implementation but the one I first came up with. It\'s giving me something between top 45% and top 80% regarding times.\n\n**Time Complexity:** **`O(NlogN)`**, N being the size of the stream.\n**Space Complexity:** **`O(M)`**\n\n```\nclass MKAverage {\n\n    private TreeMap<Integer, Integer> counts;\n    private Deque<Integer> stream;\n    private int m;\n    private int k;\n    private int totalSum = 0;\n    private int totalSize = 0;\n    \n    \n    public MKAverage(int m, int k) {\n        counts = new TreeMap<>();\n        stream = new LinkedList<>();\n        this.m = m;\n        this.k = k;\n    }\n    \n    public void addElement(int num) {\n        totalSum += num;\n        totalSize++;\n        stream.add(num);\n        if (stream.size() > m) {\n            Integer key = stream.removeFirst();\n            counts.put(key, counts.get(key) - 1);\n            totalSum -= key;\n            if (counts.get(key) == 0) counts.remove(key);\n        }\n        counts.put(num, counts.getOrDefault(num, 0) + 1);\n    }\n    \n    public int calculateMKAverage() {\n        if (totalSize < m) return -1;\n        \n        int key = counts.firstKey();\n        int lastKey = counts.lastKey();\n        int kSmall = k, kLarge = k;\n\n        int extremeSum = 0;\n\n        System.out.println(counts.toString());\n        \n        while (kSmall > 0) {\n            int toSubtractSmall = Math.min(kSmall, counts.get(key));\n            kSmall -= toSubtractSmall;\n            extremeSum += key * toSubtractSmall;\n            System.out.println(key + toSubtractSmall);\n            if (toSubtractSmall == counts.get(key)) key = counts.higherKey(key);\n        }\n\n        while (kLarge > 0) {\n            int toSubtractLarge = Math.min(kLarge, counts.get(lastKey));\n            kLarge -= toSubtractLarge;\n            extremeSum += lastKey * toSubtractLarge;\n            System.out.println(lastKey + toSubtractLarge);\n            if (toSubtractLarge == counts.get(lastKey)) lastKey = counts.lowerKey(lastKey);\n        }\n        \n        int ret = (totalSum - extremeSum) / (m - 2 * k);\n        \n        return ret;\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```
['Tree', 'Queue', 'Java']