Python3 Keeping Three Containers For Small/Middle/Large Values (Runtime 98%, Memory 94%)
Intuition\nSince this data structure deals only with the last m elements from a data stream, it\'s natural to use a deque that only stores the latest m elements
# Intuition\nSince this data structure deals only with the last m elements from a data stream, it\'s natural to use a deque that only stores the latest m elements (*self.container*). The first solution I came up was precisely that, as can be seen from the commented data block. \n\nIn that straight-forward approach, whenever a valid "calculateMKAverage" query is sent, we will sort *self.container* ad hoc in order to preserve the order of the data stream from sorting. It\'s pretty obvious why that approach is unfeasible with larger m, as each sort operation is an $$O(m log m)$$ operation. I tried implementing a basic cache that only gets refreshed when the data is changed, and the newly added value does not equal to the removed value. This however is inadequate for this question. It was this tinkering with cache that led me to the solution that I finally came up with\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nWe use *self.container* to keep track of the data stream order, and use three separate sorted containers (*self.smallest, self.middle, self.largest*) to keep track of the minimum/maximum-k elements, and the m-2k elements in the middle. \nUsing SortedList provides many crucial advantages for our purpose:\n1. The sorted nature of the elements means that add, delete and membership operations benefit from binary search algorithm (which is natively provided by the SortedList). As can be seen on https://grantjenks.com/docs/sortedcontainers/sortedlist.html, add, remove and pop operations only have $$O(log(k))$$ time complexity on SortedList\n2. Because the three containers are separately sorted, moving between smallest/middle and largest/middle becomes very easy: we know that it must happen at their respective ends (for example, when a new added value is smaller than existing values in the smallest container, it will naturally be sorted to take the index of middle[0], and the element that no longer is the smallest would sit at the index of smallest[-1] after we move the new value into the smallest container)\n3. Sorting operations have the average time complexity of $$O(n log n)$$. This means that doing a lump-sum sorting of the entire container will certainly be less efficient than doing three sortings of smaller containers($$max(O(klogk), O((m-2k)log(m-2k))$$). What\'s more, by using SortedList we aren\'t even doing a complete sorting each time! A full sorting only happens when we initialize the three containers, and all subsequent operations involve the adding and deleting of single elements, which are $$O(log(k))$$ operations.\n\nThe other optimization is keeping a running sum instead of calculating the sum of *self.middle* every time when average is queried. With any addition and deletion of element it will only impact the running_sum in 2 ways:\n1. When an element is put in the *self.middle* (either as a new element, or moving from the extremes), we add it to the running sum\n2. When an element is removed from *self.middle* (either directly removed, or moving to the extremes), we subtract it from the running sum.\n\n\nLet\'s break down what happens when a new element(*num*) gets added:\n\n1. When the container has not reached m, we simply appended *num* at the end of *self.container*. If after appending it we have reached the target size of m, we initialize the partition of values into *self.smallest, self.middle, self.largest*, and calculate the initial running sum *self.mid_sum*\n\n2. For any subsequent data stream, it will be pushed onto *self.container*, and the oldest one gets popped. After keeping track of stream order with this deque, we move our attention to how this will impact the three containers (Tip: *smallest[-1] == max(smallest), largest[0] == min(largest)*):\n- If both the popped element and the added element belong to the middle container, we don\'t have to worry about anything else: we delete the old value and add the new value to our running sum\n- If the popped element is from the middle, and the added element goes to the extremes, we will check where it will actually go to (*num_small = num<= self.smallest[-1]*). Remember, since only the k number of extreme values get discarded, after adding a new element it will now contain k+1 elements, with the one at their respective end (*max(smallest) and min(largest)*) disqualified and moved back to the middle. We then adjust the running sum based on which one moved into and which one moved out of the midle\n- If the popped element is from the extremes, we will first put the new element in the middle, and move min(middle) or max(middle) to the side the of extreme that has its element just popped. **And here\'s a pitfall: the new value can potentially update the other extreme.** Here\'s the debugging log when you didn\'t check for that: As you can see, we didn\'t check if 64938 can update the largest, resulting in 64938 incorrectly placed in the middle.\n\n```\nSortedList([8272]) SortedList([15456]) SortedList([33433])\nContainer before adding: deque([8272, 33433, 15456])\nPopped: 8272 Num: 64938\nSortedList([15456]) SortedList([64938]) SortedList([33433])\n\n```\n\n- Solving the above mentioned bug is easy: it doesn\'t hurt if we simply try to update the other extreme by moving the potential update candidate there, and pulling back the disqualified one! If the new value doesn\'t update it, nothing happens since they\'ll be pulled back, but if it does, then it will correctly update it.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(log k)$$ for *addElement* since each time it only involves a handful of operations involving adding and removing values from three SortedList.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m)$$, since we store a m-sized deque and a partition of that deque, with total size of 2m\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n# from collections import deque\n\n\n# class MKAverage:\n#     container = None\n#     m = None\n#     k = None\n#     cached = None\n#     def __init__(self, m: int, k: int):\n#         self.container = deque()\n#         self.m = m\n#         self.k = k\n#         self.cached = None\n\n#     def addElement(self, num: int) -> None:\n#         popped = None\n#         if len(self.container) < self.m:\n#             self.container.append(num)\n#         else:\n#             popped = self.container.popleft()\n#             self.container.append(num)\n#         if popped != num:\n#             self.cached = None\n\n#     def calculateMKAverage(self) -> int:\n#         if len(self.container) < self.m:\n#             return -1\n#         if self.cached is not None:\n#             return self.cached\n#         m = self.m\n#         k = self.k\n#         self.cached = int(sum(sorted(self.container)[k:m-k])/(m-2*k))\n#         return self.cached\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\nfrom collections import deque\nfrom sortedcontainers import SortedList\n\nclass MKAverage:\n\n\n    def __init__(self, m: int, k: int):\n        self.smallest = SortedList()\n        self.middle = SortedList()\n        self.largest = SortedList()\n        self.container = deque()\n        self.mid_sum = None\n        self.m = m\n        self.k = k\n \n        \n\n    def addElement(self, num: int) -> None:\n        if len(self.container) < self.m:\n            self.container.append(num)\n            if len(self.container) == self.m:\n                #initializing partition when first filled\n                sorted_result = sorted(self.container)\n                self.smallest = SortedList(sorted_result[:self.k])\n                self.middle = SortedList(sorted_result[self.k:self.m-self.k])\n                self.largest = SortedList(sorted_result[-self.k:])\n                self.mid_sum = sum(self.middle)\n        else:\n            #print ("Container before adding:", self.container)\n            popped = self.container.popleft()\n            self.container.append(num)\n            #print ("Popped:", popped, "Num:", num)\n            # if popped from middle and added to middle, don\'t worry about anything\n            if self.smallest[-1]<popped<self.largest[0] and self.smallest[-1]<num<self.largest[0]:\n                self.mid_sum+=num-popped\n                self.middle.add(num)\n                self.middle.remove(popped)\n\n                \n            # if popped from the middle and added to the extremes, update corresponding container\n            elif self.smallest[-1]<popped<self.largest[0]:\n                self.middle.remove(popped)\n                # where should num go\n                num_small = num<= self.smallest[-1]\n                if num_small:\n                    self.smallest.add(num)\n                    # element that moved to the middle\n                    moved = self.smallest.pop()\n                else:\n                    self.largest.add(num)\n                    # element that moved to the middle\n                    moved = self.largest.pop(0)\n                self.middle.add(moved)\n                self.mid_sum += moved-popped\n                \n            # if popped from the extremes, first putting the new number in the middle, then move\n            # popped from smallest\n            elif popped<= self.smallest[-1]:\n                self.smallest.remove(popped)\n                self.middle.add(num)\n                # smallest in the middle moved to smallest container\n                moved = self.middle.pop(0)\n                self.smallest.add(moved)\n                # First adding num to middle, then moving moved from middle\n                self.mid_sum += num-moved\n                # Updating the largest container\n                # moving max(middle) to largest\n                moved = self.middle.pop()\n                self.mid_sum -= moved\n                self.largest.add(moved)\n                # moving min(largest) to middle\n                moved = self.largest.pop(0)\n                self.mid_sum += moved\n                self.middle.add(moved)\n                \n            elif popped>= self.largest[0]:\n                self.largest.remove(popped)\n                self.middle.add(num)\n                # largest in the middle moved to largest container\n                moved = self.middle.pop()\n                self.largest.add(moved)\n                # First adding num to middle, then moving moved from middle\n                self.mid_sum += num-moved\n                # Updating the smallest container\n                # moving min(middle) to smallest\n                moved = self.middle.pop(0)\n                self.mid_sum -= moved\n                self.smallest.add(moved)\n                # moving max(smallest) to middle\n                moved = self.smallest.pop()\n                self.mid_sum += moved\n                self.middle.add(moved)\n\n    \n            #print (self.smallest, self.middle, self.largest)\n\n    def calculateMKAverage(self) -> int:\n        if len(self.container) < self.m:\n            return -1\n        return self.mid_sum // (self.m - 2* self.k)\n```
['Python3']