Python: Faster than 100% using 1 hash
Algorithm is fairly straightforward. Keep track of the m window with a hash. Use hash to find MK Average. Ran 4x. Faster than 100% each time and 100% less memor
Algorithm is fairly straightforward. Keep track of the m window with a hash. Use hash to find MK Average. Ran 4x. Faster than 100% each time and 100% less memory 3x (89% the other).\n\nMore Details:\n\nOn insert\n1. Increment the counter for the newest number in the hash.\n2. If we\'ve already added m elements to the hash, decrement the counter for the oldest element.\n3. Clean up unnecessary keys\n\nCalculating Average\nHash already contains exactly the m window as (k,v) where sum of values == m.\n1. Sort the keys. Keys represent the numbers in the m window.\n2. Loop through the keys from both sides simultaneously; decreasing the values of endpoints until only middle keys have v > 0.\n3. Instead of adding every number in the m window, take the product sum of k,v to save on operations. Skip the multiplication for kth largest and smallest elements in the hash.\n4. Return the average\n\nCode\n```\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.values = []\n        self.holder = {}\n\n    def addElement(self, num):\n        """\n        :type num: int\n        :rtype: None\n        """\n        self.values.append(num)\n        self.holder[num] = 1 if num not in self.holder else self.holder[num] + 1\n        if len(self.values) > self.m:\n            val = self.values[-self.m-1]\n            if self.holder[val] == 1:\n                del(self.holder[val])\n            else:\n                self.holder[val] -= 1\n\n    def calculateMKAverage(self):\n        """\n        :rtype: int\n        """\n        if len(self.values) < self.m:\n            return -1\n        \n        kbegin,kend = self.k,self.k\n        workingcopy = self.holder.copy()\n        sortedkeys = sorted(self.holder.keys())\n\n        for i,x in enumerate(sortedkeys):\n           \n            if kbegin <= 0 and kend <= 0: break\n            \n            if kbegin < workingcopy[x] and kbegin > 0:\n                workingcopy[x] -= kbegin\n                kbegin = 0\n            elif kbegin >= workingcopy[x]:\n                kbegin -= workingcopy[x]\n                workingcopy[x] = 0\n            \n            if kend < workingcopy[sortedkeys[-i-1]] and kend > 0:\n                workingcopy[sortedkeys[-i-1]] -= kend\n                kend = 0\n            elif kend >= workingcopy[sortedkeys[-i-1]]:\n                kend -= workingcopy[sortedkeys[-i-1]]\n                workingcopy[sortedkeys[-i-1]] = 0\n        \n        nums = [ k*workingcopy[k] for k in workingcopy if workingcopy[k] > 0]\n        \n        return sum(nums)//(self.m-self.k*2)\n            \n
['Python']