[Python3] 1-SortedList + Queue with a thought process.
Intuition\n To manage current m values, we can use a queue.\n But if we sort and count the middle sum on every insertion, A single Insertion will take O(MlogM) 
**Intuition**\n* To manage current m values, we can use a queue.\n* But if we sort and count the middle sum on every insertion, A single Insertion will take O(MlogM) time, O(TM log M) as total where M is the number of elements in the window, T is the total stream elements.  \n\n* So we can use the following ideas.\n\t* Idea1: Use TreeSet to keep M elements sorted.\n\t* Idea2: Incrementally update the middle value\'s sum rather than scanning multiple elements every time.\n\n**Algorithm**\n* The key part is how we can incrementally update the middle sum. We can divide the sorted list into 3 partitions like the following.\n```\n        # Array: [A | B | C]  \n\t\t#     : A -> k-smallest values.  B -> middle values.  C-> k-largest values.\n\t\t# Index range\n\t\t#       [0..k-1 | k ... m-k-1 | m-k .. m-1]\n```\n\n* And when we remove staled element from the sorted list, there are 3 possible patterns.\n\n```\n# If we remove element from C -> that does not affect the middle sum.\n#                      from B -> we lose that value, C\'s left most value become B\'s right most value so add that value to the middle sum.\n#                      from A -> we lose B\'s leftmost value and obtain C\'s leftmost value to the middle sum, since they are pushed to left.\n```\n\n* Then when we add a new value to the sorted list, there are also 3 possible patterns.\n\n```\n# If we insert element to C -> that does not affect the middle sum.\n#                         B -> we need to add that value, and lost B\'s rightmost value since it will be pushed to C.\n#                         A -> we need to add A\'s rightmost value to the middle sum and subtract B\'s rightmost value from the middle sum since they are pushed to right.\n```\n\n* An edge case you need to consider is that the sorted list contains multiple possible values. We need to use the same rule between insertion/deletion, for now, I use bisect_right method so that we can always manipulate the rightmost value.\n\n* When we remove/add elements to sorted list, we can update the middle sum based on its deletion/insertion index.\n\n**Code Example**\n```\nfrom sortedcontainers import SortedList\nfrom collections import deque\n\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.middleSum = 0\n        self.queue = deque()\n        self.sortedValues = SortedList()\n        self.m = m\n        self.k = k   \n\n    def addElement(self, num: int) -> None: # Total O(mlogm)\n        # [A | B | C]\n        # [0..k-1 | k   m-k-1 | m-k .. m-1]\n        # A -> k-smallest B-> middle C-> k-largest\n\n        if len(self.queue) < self.m: \n            self.queue.append(num)\n            self.sortedValues.add(num)\n\t\t    # This initialization will be triggered only once when the queue size become m-1 to m.\n            if len(self.queue) == self.m: # O(mlogm) for initialization.\n                self.middleSum = sum(self.sortedValues[self.k:(self.m - self.k)])\n            return\n        \n        # After the queue size become m, each Operation cost is O(logm)\n        remove_val = self.queue.popleft()\n            \n        # Phase1: Remove\n        removal_idx = self.sortedValues.bisect_right(remove_val) - 1 # pick right most element.\n        if removal_idx < self.k: #  on A\n            self.middleSum -= self.sortedValues[self.k] # leftmost B\n            self.middleSum += self.sortedValues[self.m - self.k] # leftmost C\n        elif removal_idx > self.m - self.k - 1: # on C\n            pass\n        else: # on B\n            self.middleSum -= remove_val\n            self.middleSum += self.sortedValues[self.m - self.k] # leftmost C\n        \n        self.sortedValues.remove(remove_val)\n        \n        # Phase2: Insert\n        self.queue.append(num)\n        \n        insertion_idx = self.sortedValues.bisect_right(num)\n        if insertion_idx < self.k: # on A\n            self.middleSum += self.sortedValues[self.k - 1] # rightmost A\n            self.middleSum -= self.sortedValues[self.m - self.k - 1] # rightmost B\n        elif insertion_idx > self.m - self.k - 1: # on C\n            pass\n        else: # on B\n            self.middleSum += num\n            self.middleSum -= self.sortedValues[self.m - self.k - 1] # rightmost B\n            \n        self.sortedValues.add(num)       \n\n    def calculateMKAverage(self) -> int: # O(1)\n        if len(self.queue) < self.m:\n            return -1\n        return self.middleSum // (self.m - (2 * self.k))\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```\n\n**Complexity Analysis**\n\nTime:\n* Total O(TlogM)  # T = Total elements in a stream.  M = Total elements in a window.\n\t* Initialization: O(MlogM)\n\t* Insertion: O(logM)\n\t* Query: O(1)\n\nMemory:\n* O(M) for queue / sorted list\n\n**Runtime History**\n* Runtime: 3212 ms, faster than 48.67% of Python3 online submissions for Finding MK Average.\n* Memory Usage: 49.6 MB, less than 74.34% of Python3 online submissions for Finding MK Average.\n\n\n\n\n
['Queue', 'Python3']