Python, Binary search and double-ended queue. Showing clear thread of thoughts
Intuition\n\nThought 1: We start from the naive solution\n Idea: Keep a container of m elements (data structure: double-ended queue, probably a doubly-linked li
# Intuition\n\nThought 1: We start from the naive solution\n* Idea: Keep a container of m elements (data structure: double-ended queue, probably a doubly-linked list in exact implementation)\n* AddElement -> cost O(1)\n* calculateMKAverage -> sort (O(m log m)))\n\nThought 2: Can we do better for calculate MKAverage?\n* Idea: Keep an additional structure, which is sorted\n* AddElement -> find the element to remove O(log m), add the element O(log m).\n(Note: Actually I noticed that cPython list is not a implementation that allows us to insert/remove an element in constant time. An exact data structure suitable would be a binary search tree.)\n* calculateMKAverage -> O(m)\n\nThought 3: MKAverage is still slower than adding element. Can we do even better for calulating MKAverage?\n* Idea: Keep a value of the sum of the elements qualified. Update the sum everytime we add an element.\n\n# Approach\n\nHow do we do even better for calculating MKAverage?\n1. when we remove an element A, if A\n    - if among smallest (largest) k, we reduce sum by k+1 smallest (largest) value.\n    - if not, we reduce sum by A.\n2. when we add an element B, if B\n    - if among smallest (largest) k, we add to sum the k+1 smallest (largest) value.\n    - if not, we add B to sum.\n* AddElement -> Still O(log m), as the additional overhead is constant.\n* calculateMKAverage -> O(1).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n* AddElement -> Still O(log m), as the additional overhead is constant.\n* calculateMKAverage -> O(1).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n* O(m) for the deque and sorted list that we keep.\n\n# Code\n```\nimport bisect\nfrom collections import deque\n\nclass MKAverage:\n\n    # Naive\n    # Keep a container of m elements (data structure: doubl-ended queue)\n    # AddElement -> cost O(1)\n    # calculateMKAverage -> sort (O(m log m)))\n\n    # Can we do better for calculate MKAverage?\n    # Keep an additional structure, which is sorted\n    # AddElement -> find the element to remove O(log m), add the element O(log m)\n    # calculateMKAverage -> O(m)\n\n    # Can we do even better for calulating MKAverage?\n    # Keep a value of the sum of the elements qualified.\n    # Update the average everytime we add an element.\n    # How to?\n    # 1. when we remove an element A, if A\n    # - if among smallest (largest) k, we reduce sum by k+1 smallest (largest) value.\n    # - if not, we reduce sum by A\n    # 2. when we add an element B, if B\n    # - if among smallest (largest) k, we add to sum the k+1 smallest (largest) value.\n    # - if not, we add B to sum.\n    # calculateMKAverage -> O(1)\n\n    def __init__(self, m: int, k: int):\n\n        self.m = m\n        self.k = k\n\n        self.deque = deque()\n        self.sorted = list()\n        self.total = 0\n        \n\n    def addElement(self, num: int) -> None:\n\n        if len(self.deque) < self.m:\n            self.deque.append(num)\n            bisect.insort(self.sorted, num)\n            if len(self.deque) == self.m:\n                self.total = sum(self.sorted[self.k:-self.k]) \n        else:\n            # remove element\n            v = self.deque.popleft()\n            index = bisect.bisect_left(self.sorted, v)\n            if index < self.k:\n                self.total -= self.sorted[self.k]\n            elif index >= self.m - self.k:\n                self.total -= self.sorted[-self.k-1]\n            else:\n                self.total -= v\n            self.sorted.pop(index)\n\n            # add element\n            self.deque.append(num)\n            index = bisect.bisect_left(self.sorted, num)\n            self.sorted.insert(index, num)\n            if index < self.k:\n                self.total += self.sorted[self.k]\n            elif index >= self.m - self.k:\n                self.total += self.sorted[-self.k - 1]\n            else:\n                self.total += num\n\n\n    def calculateMKAverage(self) -> int:\n\n        if len(self.deque) < self.m:\n            return - 1\n\n        return int(self.total / (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```
['Python3']