Don't use SortedList in interviews. Three MinMaxHeap. Add: O(logM + log(M-2K)), Calc:O(1). Beats 96%
Intuition\n Describe your first thoughts on how to solve this problem. \nIn the inteview, usually we cannot use SortedList which is not in standard libraries. D
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn the inteview, usually we cannot use SortedList which is not in standard libraries. Doublecheck your goal, passing interviews or just solving leetcode?\n\n# Approach\nSplit data into 3 parts. And make each part as MinMaxHeap so that we can get pop min/max values by average O(logN).\nMinMaxHeap can be written with lazy deletion.\nCodes are long but must be faily easy.\n\n# Complexity\n- Time complexity:\nAddElement: O(logM + log(M-2K))\nCalculateMKAverage: O(1)\n\n- Space complexity:\nO(N)\n\n# Code\n```\nfrom heapq import heappush, heappop\nfrom collections import deque\nclass MinMaxHeap:\n    def __init__(self):\n        self.minheap = []\n        self.maxheap = []\n        self.mindeletings = []\n        self.maxdeletings = []\n        self.len = 0\n        self.sum = 0\n\n    def push(self, val):\n        heappush(self.minheap, val)\n        heappush(self.maxheap, -val)\n        self.len += 1\n        self.sum += val\n\n    def pop_min(self):\n        self.balance_min()\n        val = heappop(self.minheap)\n        \n        heappush(self.maxdeletings, -val)\n        self.len -= 1\n        self.sum -= val\n        return val\n\n    def pop_max(self):\n        self.balance_max()\n        val = -heappop(self.maxheap)\n\n        heappush(self.mindeletings, val)\n        self.len -= 1\n        self.sum -= val\n        return val\n    \n    def min(self):\n        self.balance_min()\n        if len(self.minheap) == 0:\n            return 10000000\n        return self.minheap[0]\n\n    def max(self):\n        self.balance_max()\n        if len(self.maxheap) == 0:\n            return -10000000\n        return -self.maxheap[0]\n\n    def balance_min(self):\n        while len(self.mindeletings) > 0 and self.minheap[0] == self.mindeletings[0]:\n            heappop(self.mindeletings)\n            heappop(self.minheap)\n    \n    def balance_max(self):\n        while len(self.maxdeletings) > 0 and self.maxheap[0] == self.maxdeletings[0]:\n            heappop(self.maxdeletings)\n            heappop(self.maxheap)\n\n    def delete(self, val): # doesn\'t care if it exits\n        heappush(self.mindeletings, val)\n        heappush(self.maxdeletings, -val)\n        self.len -= 1\n        self.sum -= val\n\nclass MKAverage:\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.ar = deque()\n        self.p1 = MinMaxHeap()\n        self.p2 = MinMaxHeap()\n        self.p3 = MinMaxHeap()\n\n    def addElement(self, num: int) -> None:\n        if len(self.ar) < self.m:\n            self.ar.append(num)\n            if len(self.ar) == self.m: # initialize\n                sorted_ar = sorted(self.ar)\n                for i in range(self.m):\n                    if i < self.k:\n                        self.p1.push(sorted_ar[i])\n                    elif i < self.m - self.k:\n                        self.p2.push(sorted_ar[i])\n                    else:\n                        self.p3.push(sorted_ar[i])\n            return\n            \n        # handle ar\n        val = self.ar.popleft()\n        self.ar.append(num)\n\n        # delete from p1, p2, or p3\n        if val <= self.p1.max():\n            self.p1.delete(val)\n        elif val <= self.p2.max():\n            self.p2.delete(val)\n        else:\n            self.p3.delete(val)\n\n        # push to p1, p2, or p3\n        if num < self.p1.max():\n            self.p1.push(num)\n        elif num <= self.p2.max():\n            self.p2.push(num)\n        else:\n            self.p3.push(num)\n\n        # rebalance\n        if self.p1.len > self.k:\n            self.p2.push(self.p1.pop_max())\n        if self.p3.len > self.k:\n            self.p2.push(self.p3.pop_min())\n\n        if self.p2.len > self.m - 2 * self.k:\n            if self.p1.len < self.k:\n                self.p1.push(self.p2.pop_min())\n            if self.p3.len < self.k:\n                self.p3.push(self.p2.pop_max())                \n\n    def calculateMKAverage(self) -> int:\n        if len(self.ar) < self.m:\n            return -1\n        return self.p2.sum // self.p2.len\n\n\n# Your MKAverage object will be instantiated and called as such:\n# obj = MKAverage(m, k)\n# obj.addElement(num)\n# param_2 = obj.calculateMKAverage()\n```
['Heap (Priority Queue)', 'Python3']