A sub optimal solution which is possible to code fully in an interview
Intuition\n Describe your first thoughts on how to solve this problem. \nWhile solving the problem I got the intuition to maintain three heaps, or dividing an a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhile solving the problem I got the intuition to maintain three heaps, or dividing an array to three parts and keeping sum of these tree parts and update if any element is added or deleted from each. But I was finding it very difficult to convert my intuition into code in a time bound manner. \nSo I thought if it were an interview, rather than ending up not coding anything to achieve O(1) sum, I may very well code out a non optimal solution. If someone else is also feeling lost and demotivated looking at all the other solutions, here is one which gets accepted, even if not the best! :) Hope it gives you the moral boost to have patience and understand the optimal one, as I am going to do now. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nMaintain a deque to act as a FIFO container to tell us the relevant m elements. We store the number as entry. Whenever we have more than m elements, we discard that number from sortedlist. This setup is very similar to an LRU cache. \nTo calculate the average, I go sub optimal and directly take sum of middle m-2k elements. \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nPush and pop into a deque is O(1). For sorted list insertion and deletion is O(logn). We will keep max m elements in the list at a time, so O(logm). The biggest bottleneck on time is calculation of sum which is O(m-2k) Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m) for the sorted list. Also O(m) for the deque().\n# Code\n```\nfrom sortedcontainers import SortedList\nclass MKAverage(object):\n\n    def __init__(self, m, k):\n        """\n        :type m: int\n        :type k: int\n        """\n        self.m = m \n        self.k = k \n        self.elements = SortedList()\n        self.deque = deque() \n\n    def addElement(self, num):\n        """\n        :type num: int\n        :rtype: None\n        """\n        if len(self.elements) >= self.m:\n            oldNum = self.deque.popleft()\n            self.elements.discard(oldNum)\n        # idx = bisect.bisect_left(self.elements, num)\n        self.elements.add(num)\n        self.deque.append(num)\n\n    def calculateMKAverage(self):\n        """\n        :rtype: int\n        """\n        if len(self.elements) < self.m:\n            return -1 \n        Leftover = self.elements[self.k:-self.k]\n        return int(sum(Leftover)/len(Leftover))\n        \n\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```
['Doubly-Linked List', 'Python']