Java Solution | PriorityQueue + Lazy Deletion | O(log M) add, O(1) calculate | Detailed Explanations
The structure of this solution may be a little complex, but easy to understand. Here, I keep 4 priority_queues to record the smallest k elements, (m -k2) elment
The structure of this solution may be a little complex, but easy to understand. Here, I keep 4 priority_queues to record the smallest k elements, (m -k*2) elments in middle window and the largest k elements. For each operation, I just need to check which priority_queue the queue_in number and queue_out number locates, and conduct the transmission process. Here is a demonstration figure for this solution.\n![image](https://assets.leetcode.com/users/images/49697ece-380c-483d-9f71-34f11353621f_1618116262.3197303.png)\nSince priority_queue cannot directly delete a specific element, here I employ a lazy deletetion technique. Everytime I want to delete an element from a priority_queue, I use a hash table to record the elements required to delete. When I want to poll an element from such priority_queue, I would first do the deletion process if the top element of such priority_queue is contained in the delete table.\n\nHere take the sample example to explaine the process.\nInput\n["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]\n[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]\nOutput\n[null, null, null, -1, null, 3, null, null, null, 5]\nSteps:\n1. Initial: left_maxHeap: [], middle_minHeap: [], middle_maxHeap: [], right_minHeap: [], sum : 0, vals_queue: []\n2. Add 3: left_maxHeap: [], middle_minHeap: [], middle_maxHeap: [], right_minHeap: [], sum : 0, vals_queue: [3]\n3. Add 1: left_maxHeap: [], middle_minHeap: [], middle_maxHeap: [], right_minHeap: [], sum : 0, vals_queue: [3, 1]\n4. Calculate: Since size(vals_queue) < m, return -1;\n5. Add 1: left_maxHeap: [], middle_minHeap: [], middle_maxHeap: [], right_minHeap: [], sum : 0, vals_queue: [3, 1, 10]\n\t* Since size(vals_queue) == m, initialize all the priority_queues. left_maxHeap: [1], middle_minHeap: [3], middle_maxHeap: [3], right_minHeap: [10], sum : 3, vals_queue: [3, 1, 10]\n6. Calculate: return sum / (m - 2k) = 3\n7. Add 5: vals_queue: [3, 1, 10, 5]. Required to poll 3 from left.\n\t* \tPoll 3: Since 3 is located in middle priority_queue, just delete it from middle_minHeap and middle_maxHeap. Update the sum = 0.\n\t* \tAdd 5: Since 5 is also located in middle priority_queue, just add it to middle_minHeap and middle_maxHeap. Update the sum = 5.\n\t* \tleft_maxHeap: [1], middle_minHeap: [5], middle_maxHeap: [5], right_minHeap: [10], vals_queue: [1, 10, 5], sum: 5.\n8. Add 5: vals_queue: [1, 10, 5, 5]. Required to poll 1 from left.\n\t*  Poll 1: Since 1 is located in left priority_queue, delete it from left priority_queue and transmit the smallest value from middle_minHeap to the left priority_queue. Here remember this value also needed to be deleted from the middle_maxHeap to syncronize. Update the sum = 0.\n\t*  Add 5: Since 5 is located in left priority_queue, first transmit the largest value from left priority_queue to the middle priority_queues and add 5 to the left priority_queue. Update the sum = 5.\n\t*  left_maxHeap: [5], middle_minHeap: [5], middle_maxHeap: [5], right_minHeap: [10], vals_queue: [10, 5, 5], sum: 5.\n9. Add 5: vals_queue: [10, 5, 5, 5]. Required to poll 10 from left.\n\t*  Poll 10: Since 10 is located in right priority_queue, delete it from right priority_queue and transmit the largest value from middle_maxHeap to the right priority_queue. Here remember this value also needed to be deleted from the middle_minHeap to syncronize. Update the sum = 0.\n\t*  Add 5: Since 5 is located in left (right, either is ok) priority_queue, first transmit the largest value from left priority_queue to the middle priority_queues and add 5 to the left priority_queue. Update the sum = 5.\n\t*  left_maxHeap: [5], middle_minHeap: [5], middle_maxHeap: [5], right_minHeap: [5], vals_queue: [5, 5, 5], sum: 5.\n10. Calculate: return sum / (m - 2k) = 5\n\nFor each add operation (despite the initialization), I do 2 priority_queue manipulation process which would cost O(log m) time. The lazy deletion process can be amortized to all add operations which should only cost O(1) time in average.\nFor each calculation operation, it cost O(1) time.\n\nIt it helps you, please upvote. Thanks!\n\n```java\nclass MKAverage {\n    PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);\n    PriorityQueue<Integer> right = new PriorityQueue<>((a, b) -> a - b);\n    PriorityQueue<Integer> minMiddle = new PriorityQueue<>((a, b) -> a - b);\n    PriorityQueue<Integer> maxMiddle = new PriorityQueue<>((a, b) -> b - a);\n    Queue<Integer> vals = new LinkedList<>();\n    Map<Integer, Integer> deleteLeft = new HashMap<>(), deleteRight = new HashMap<>(), deleteMinMiddle = new HashMap<>(), deleteMaxMiddle = new HashMap<>();\n    \n    long sum;\n    int m, k;\n    boolean flag;\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n        sum = 0;\n        flag = false;\n    }\n    \n    public void addElement(int num) {\n        vals.offer(num);\n        \n        if (!flag && vals.size() == m) {\n            initialize();\n            flag = true;\n        }\n        else if (flag) {\n            int lv = vals.poll();\n            update(left, deleteLeft);\n            update(right, deleteRight);\n            if (!left.isEmpty() && left.peek() >= lv) {\n                update(minMiddle, deleteMinMiddle);\n                int v = minMiddle.poll();\n                deleteMaxMiddle.put(v, deleteMaxMiddle.getOrDefault(v, 0) + 1);\n                left.offer(v);\n                deleteLeft.put(lv, deleteLeft.getOrDefault(lv, 0) + 1);\n                sum -= v;\n            }\n            else if (!right.isEmpty() && right.peek() <= lv) {\n                update(maxMiddle, deleteMaxMiddle);\n                int v = maxMiddle.poll();\n                deleteMinMiddle.put(v, deleteMinMiddle.getOrDefault(v, 0) + 1);\n                right.offer(v);\n                deleteRight.put(lv, deleteRight.getOrDefault(lv, 0) + 1);\n                sum -= v;\n            }\n            else {\n                deleteMinMiddle.put(lv, deleteMinMiddle.getOrDefault(lv, 0) + 1);\n                deleteMaxMiddle.put(lv, deleteMaxMiddle.getOrDefault(lv, 0) + 1);\n                sum -= lv;\n            }\n            \n            update(left, deleteLeft);\n            update(right, deleteRight);\n            if (!left.isEmpty() && left.peek() >= num) {\n                int v = left.poll();\n                minMiddle.offer(v);\n                maxMiddle.offer(v);\n                left.offer(num);\n                sum += v;\n            }\n            else if (!right.isEmpty() && right.peek() <= num) {\n                int v = right.poll();\n                minMiddle.offer(v);\n                maxMiddle.offer(v);\n                right.offer(num);\n                sum += v;\n            }\n            else {\n                minMiddle.offer(num);\n                maxMiddle.offer(num);\n                sum += num;\n            }\n        }\n    }\n    \n    public int calculateMKAverage() {\n        // System.out.println(sum);\n        return flag? (int)(sum / (m - 2 * k)) : -1;\n    }\n    \n    private void initialize() {\n        int i;\n        for (i = 0; i < m; ++i) {\n            int v = vals.poll();\n            minMiddle.offer(v);\n            maxMiddle.offer(v);\n            sum += v;\n            vals.offer(v);\n        }\n        i = 0;\n        while (i < k) {\n            update(minMiddle, deleteMinMiddle);\n            int v = minMiddle.poll();\n            left.offer(v);\n            deleteMaxMiddle.put(v, deleteMaxMiddle.getOrDefault(v, 0) + 1);\n            sum -= v;\n            i ++;\n        }\n        \n        i = 0;\n        while (i < k) {\n            update(maxMiddle, deleteMaxMiddle);\n            int v = maxMiddle.poll();\n            right.offer(v);\n            deleteMinMiddle.put(v, deleteMinMiddle.getOrDefault(v, 0) + 1);\n            sum -= v;\n            i ++;\n        }\n    }\n    \n    private void update(PriorityQueue<Integer> pq, Map<Integer, Integer> delete) {\n        while (!pq.isEmpty() && delete.containsKey(pq.peek()) && delete.get(pq.peek()) > 0) {\n            int v = pq.poll();\n            delete.put(v, delete.get(v) - 1);\n            if (delete.get(v) == 0)\n                delete.remove(v);\n        }\n    }\n}\n```
['Hash Table', 'Heap (Priority Queue)', 'Java']