Python SortedList - intuitive logic and explanation
Algorithm:\n1. Maintaina queue for keeping items in stream order and 3 sorted lists - lesser, mid and greater for keeping track of the k lesser items, k greater
Algorithm:\n1. Maintaina queue for keeping items in stream order and 3 sorted lists - lesser, mid and greater for keeping track of the k lesser items, k greater items and m-2k selected items that need to be averaged\n2. When the stream size exceeds m, we need to remove the oldest entry from the stream i.e. the first entry\n\ta. This entry could be in the lesser, mid or greater lists. We simply try each of them. This is ok because we will be balancing their size while adding the new item\n3. Just add the item to the queue and also to the greater list. \n\ta. Then, trickle down the first entry in the greater list to the mid list and similarly from the mid list to the lesser list. \n\tb, Then, if the lesser list size is greater than k, bubble up the last entry to the mid list and similarly from the mid list to the greater list\n\tc. The trickling down ensures that a global sorting order is maintained across the 3 lists and the bubbling up ensures that their sizes remain balanced\n4.  For each change in the mid list, keep `self.sum` updated\n5.  Return `self.sum` divided by m - 2k as the average\n\n```\nfrom sortedcontainers import SortedList\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.stream = []\n        self.lesser = SortedList()\n        self.mid = SortedList()\n        self.greater = SortedList()\n        self.m = m\n        self.k = k\n        self.sum = 0        \n\n    def addElement(self, num: int) -> None:\n        self.stream.append(num)\n        \n        if len(self.stream) > self.m:\n            # remove oldest entry from stream\n            old = self.stream.pop(0)\n            \n            # the oldest entry could be anywhere in the 3 sorted lists\n            if old in self.lesser:\n                self.lesser.remove(old)\n            elif old in self.mid:\n                self.mid.remove(old)\n                self.sum -= old\n            else:\n                self.greater.remove(old)\n        \n        # always add new entry to the greatest list\n        # and let it trickle down to mid and lowest lists\n        self.greater.add(num)\n        extra = self.greater.pop(0)\n        self.mid.add(extra)\n        self.sum += extra\n        extra = self.mid.pop(0)\n        self.sum -= extra\n        self.lesser.add(extra)\n        \n        # if lesser list has more than k entries,\n        # bubble up last entry to mid\n        if len(self.lesser) > self.k:\n            extra = self.lesser.pop()\n            self.mid.add(extra)\n            self.sum += extra\n            \n        # if mid list has more than m - 2k entries,\n        # bubble up last entry to greatest\n        if len(self.mid) > self.m - 2 * self.k:\n            extra = self.mid.pop()\n            self.sum -= extra\n            self.greater.add(extra)\n            \n\n    def calculateMKAverage(self) -> int:\n        if len(self.stream) < self.m:\n            return -1\n        return self.sum // (self.m - 2*self.k)\n        \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```
['Python', 'Python3']