4 heaps python solution
\n# Approach\nUse 4 heaps\n max heap for lowwer k elements\n max and max heaps for middle elements\n min heap for higher k elements\n\n\n# Complexity\n addEleme
\n# Approach\nUse 4 heaps\n* max heap for lowwer k elements\n* max and max heaps for middle elements\n* min heap for higher k elements\n\n\n# Complexity\n* addElement - O(log(n))\n* calculateMKAverage - O(1)\n\n- Space complexity:\n* for heaps = 4*O(m)\n* for presence checker map = 3*O(m)\n* sor stack = O(m)\n* Total - 8*O(m)\n\n# Code\n```python3 []\nfrom collections import deque\nfrom collections import defaultdict as dd\nimport heapq\nclass MKAverage:\n    m,k = 0,0\n    pres_in_lower_k = dd(int)\n    pres_in_higher_k = dd(int)\n    pres_in_middle = dd(int)\n\n    elements_in_middle = 0\n    elements_in_lower_k = 0\n    elements_in_higher_k = 0\n\n    lower_k_max_heap = []\n    higher_k_min_heap = []\n    middle_min_heap = []\n    middle_max_heap = []\n\n    middle_sum = 0\n\n    s = deque()\n\n    def __init__(self, m: int, k: int):\n        self.m, self.k = m,k\n\n        self.pres_in_lower_k = dd(int)\n        self.pres_in_higher_k = dd(int)\n        self.pres_in_middle = dd(int)\n\n        self.elements_in_middle = 0\n        self.elements_in_lower_k = 0\n        self.elements_in_higher_k = 0\n\n        self.lower_k_max_heap = []\n        self.higher_k_min_heap = []\n        self.middle_min_heap = []\n        self.middle_max_heap = []\n\n        self.middle_sum = 0\n        self.s = deque()\n\n    def addInitialElements(self,num):\n        heapq.heappush(self.lower_k_max_heap, -num)\n        self.elements_in_lower_k+=1\n        self.pres_in_lower_k[num] += 1\n\n        if self.elements_in_lower_k>self.k:\n            # remove from lower k elements\n            top = -heapq.heappop(self.lower_k_max_heap)\n            self.elements_in_lower_k -= 1\n            self.pres_in_lower_k[top] -= 1\n\n            # add in upper k elements\n            heapq.heappush(self.middle_min_heap, top)\n            heapq.heappush(self.middle_max_heap, -top)\n            self.elements_in_middle+=1\n            self.pres_in_middle[top] += 1\n            self.middle_sum += top\n\n            if self.elements_in_middle > self.m - (2*self.k):\n\n                #remove from middle\n                middle_top = -heapq.heappop(self.middle_max_heap)\n                self.elements_in_middle-=1\n                self.pres_in_middle[middle_top] -= 1\n                self.middle_sum -= middle_top\n\n                #add in higher queue\n                heapq.heappush(self.higher_k_min_heap, middle_top)\n                self.pres_in_higher_k[middle_top] += 1\n                self.elements_in_higher_k += 1\n\n    def addElementAndBalanceHeap(self,num): \n        # print("val",num)\n        # self.print_data()\n        heapq.heappush(self.lower_k_max_heap, -num)\n        self.elements_in_lower_k+=1\n        self.pres_in_lower_k[num] += 1\n\n        if self.elements_in_lower_k > self.k:\n            top = -heapq.heappop(self.lower_k_max_heap)\n            self.elements_in_lower_k -= 1\n            self.pres_in_lower_k[top] -= 1\n\n            heapq.heappush(self.middle_min_heap, top)\n            heapq.heappush(self.middle_max_heap, -top)\n            self.elements_in_middle+=1\n            self.pres_in_middle[top] += 1\n            self.middle_sum += top\n\n        self.sanitize_heap()\n        if self.lower_k_max_heap and self.middle_min_heap and -self.lower_k_max_heap[0]>self.middle_min_heap[0]:\n            lower_max, middle_min = -heapq.heappop(self.lower_k_max_heap),heapq.heappop(self.middle_min_heap)\n            heapq.heappush(self.lower_k_max_heap, -middle_min)\n            heapq.heappush(self.middle_min_heap, lower_max)\n            heapq.heappush(self.middle_max_heap, -lower_max)\n            self.pres_in_middle[middle_min] -= 1\n            self.pres_in_middle[lower_max] += 1\n            self.pres_in_lower_k[middle_min] += 1\n            self.pres_in_lower_k[lower_max] -= 1\n            self.middle_sum += lower_max - middle_min\n\n        self.sanitize_heap()\n\n        if self.elements_in_middle > self.m - (2*self.k):\n            middle_top = -heapq.heappop(self.middle_max_heap)\n            self.elements_in_middle -= 1\n            self.pres_in_middle[middle_top] -= 1\n            self.middle_sum -= middle_top\n\n            heapq.heappush(self.higher_k_min_heap, middle_top)\n            self.pres_in_higher_k[middle_top] += 1\n            self.elements_in_higher_k += 1\n\n        self.sanitize_heap()\n\n        if self.middle_max_heap and self.higher_k_min_heap and -self.middle_max_heap[0]>self.higher_k_min_heap[0]:\n            middle_max, higher_min = -heapq.heappop(self.middle_max_heap),heapq.heappop(self.higher_k_min_heap)\n            heapq.heappush(self.middle_max_heap, -higher_min)\n            heapq.heappush(self.middle_min_heap, higher_min)\n            heapq.heappush(self.higher_k_min_heap, middle_max)\n            self.pres_in_middle[middle_max] -= 1\n            self.pres_in_middle[higher_min] += 1\n            self.pres_in_higher_k[middle_max] += 1\n            self.pres_in_higher_k[higher_min] -= 1\n            self.middle_sum += higher_min - middle_max\n        # print("after") \n        # self.print_data()\n\n\n    def remove_element(self):\n        element_to_be_removed = self.s.popleft()\n        # element poped from lower k elements\n        if self.lower_k_max_heap and -self.lower_k_max_heap[0] >= element_to_be_removed:\n            self.elements_in_lower_k-=1\n            self.pres_in_lower_k[element_to_be_removed] -= 1\n            return\n        \n        if self.middle_max_heap and -self.middle_max_heap[0] >= element_to_be_removed:\n            self.elements_in_middle-=1\n            self.pres_in_middle[element_to_be_removed] -= 1\n            self.middle_sum -= element_to_be_removed\n            return \n\n        self.pres_in_higher_k[element_to_be_removed] -= 1\n        self.elements_in_higher_k -= 1\n        \n\n\n\n\n\n    def addElement(self, num: int) -> None:\n        self.s.append(num)\n        if self.elements_in_middle + self.elements_in_lower_k + self.elements_in_higher_k  < self.m:\n            self.addInitialElements(num)\n            return\n        self.sanitize_heap()\n        self.remove_element()\n        self.sanitize_heap()\n        self.addElementAndBalanceHeap(num)\n        \n\n\n\n\n\n\n        \n\n        \n\n    def calculateMKAverage(self) -> int:\n        if self.elements_in_middle + self.elements_in_lower_k + self.elements_in_higher_k  < self.m:\n            return -1\n\n        return self.middle_sum//(self.m-(2*self.k))\n        \n    def sanitize_heap(self):\n        while self.lower_k_max_heap and self.pres_in_lower_k[-self.lower_k_max_heap[0]] == 0:\n            heapq.heappop(self.lower_k_max_heap)\n\n        while self.middle_max_heap and self.pres_in_middle[-self.middle_max_heap[0]] == 0:\n            heapq.heappop(self.middle_max_heap)\n        \n        while self.middle_min_heap and self.pres_in_middle[self.middle_min_heap[0]] == 0:\n            heapq.heappop(self.middle_min_heap)\n        \n        while self.higher_k_min_heap and self.pres_in_higher_k[self.higher_k_min_heap[0]] == 0:\n            heapq.heappop(self.higher_k_min_heap)\n\n    def print_data(self):\n        print(" lower ")\n        print(self.pres_in_lower_k,self.elements_in_lower_k)\n        print(self.lower_k_max_heap)\n        print(" middle ")\n        print(self.pres_in_middle,self.elements_in_middle)\n        print(self.middle_min_heap, self.middle_max_heap)\n        print(self.middle_sum)\n        print("last")\n        print(self.pres_in_higher_k,self.elements_in_higher_k)\n        print(self.higher_k_min_heap)\n        print()\n        print()\n```
['Python3']