Solution using BST. Easy to understand
Intuition\nUse BST as we are keeping track of sorted items. \n\n# Approach\nThere can be multiple approaches to solve this problem. Let me describe three approa
# Intuition\nUse BST as we are keeping track of sorted items. \n\n# Approach\nThere can be multiple approaches to solve this problem. Let me describe three approaches (note that first two approaches lead to TLE here):\n\n1. Brute force: We can do exactly as the problem says. Maintain a list of all elements. When an add operation comes, append to the list. When a get avg operation comes, slice out last "m" elements, sort the m elements, slice out m-2k elements from middle and return the average of this m-2k elements.\n\nTime complexity of this approach:\nFor One Add: O(1)\nFor One Get: O( m + m log m + (m-2k) ) = O( mlog m)\n\n2. Use two hashmaps: Instead of sorting m elements and slicing out m-2k elements we can maintain sliding window of last  m elements using a queue. When adding a new element if the queue size becomes greater than m remove the leftmost element from queue. When calculating the average, construct a min-heap and max-heap of size k and keep track of cumulative sum of these m elements. Then sum of m-2k elements = cumulative_sum-(sum of elements from min heap) - (sum of elements from max heap)\n\nTime complexity:\nOne Get: O( m log k)\n\n3. Use BST: Since we need a sorted list of m elements, we can use a BST for it. For Add operation, add the new element to BST and remove the first element that went out of sliding window of size m. \n\nFor Get operation, get the middle m-2k elements and return the average. However if you do this naively you will get TLE. Instead keep a track of cumulative sum and subtract the sum of k elements from this cumulative sum and then get the average\n\nTC : \nOne Add: (log m)\nOne Get: O(k)\n\n```\nimport sortedcontainers\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.all_elements = []\n        self.bst = sortedcontainers.SortedList()\n        self.m = m\n        self.k = k\n        self.m_sum = 0\n\n    def addElement(self, num: int) -> None:\n        self.all_elements.append(num)\n        self.m_sum += num\n        self.bst.add(num)\n        if len(self.bst) == self.m+1:\n            self.bst.remove(self.all_elements[-(self.m+1)])\n            self.m_sum -= self.all_elements[-(self.m+1)]\n        \n        \n\n    def calculateMKAverage(self) -> int:\n        if len(self.all_elements) < self.m:\n            return -1\n        min_sum = sum(self.bst[:self.k])\n        max_sum = sum(self.bst[-self.k:])\n        return (self.m_sum-min_sum-max_sum) // (self.m-2*self.k)\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```
['Python3']