Simple 97.11% O(n log n) Python3 solution with queue, map and two pointers
Hey guys, this is my first time posting here and english is not my first language, hopefully i can be clear but i think the code is simple enough\n \n\n# Intuit
Hey guys, this is my first time posting here and english is not my first language, hopefully i can be clear but i think the code is simple enough\n \n![Sem t\xEDtulo.png](https://assets.leetcode.com/users/images/423b1896-2b52-420d-b72f-f6a4f409b58d_1714441493.5260954.png)\n# Intuition\nAt first it did it the brute force way, just adding the elements to a first in, first out queue and keeping a separate count and sum but it would exceed the maximum time alloted. Then i had the idea to keep count of how many times each element appeared in the queue with a map, since for the average calculation we would have to sort it anyway to remove the k greater and smaller elements. this also helped with the sorting because then we dont need to sort the full queue, only one of each unique element.\n\n# Approach\nFirst we create a queue, a counter and a map. We use the queue so we know wich element is the oldest one added, the counter is so we dont need to run through the queue to know if we exceed the size, and we\'ll use the map later to calculate the average.\n```\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.queue = collections.deque()\n        self.count = 0\n        self.quantities = {}    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.queue = collections.deque()\n        self.count = 0\n        self.quantities = {}\n```\nWhen we add a new element, we keep count of how many of those elements are in the queue using the map. if the queue is bigger than m, we remove the older element of the queue and then update it\'s counter\n```\n def addElement(self, num: int) -> None:\n        self.queue.append(num)\n        self.quantities[num] = self.quantities[num] + 1 if num in self.quantities else 1\n        if self.count >= self.m:\n            first = self.queue.popleft()\n            self.quantities[first] -= 1\n        else:\n            self.count += 1\n        \n```\nNow to calculate the average. here, **we sort the map keys so we know the order of the elements in the queue, and remove the k largest and smaller elements from the map counter, not the queue**.\n```\ndef calculateMKAverage(self) -> int:\n    if self.count < self.m:\n        return -1\n    #the order of unique elements in the queue, we know the quantity  on the map\n    _list = sorted(self.quantities.keys())\n    #we keep the original queue intact for later operations\n    copy = self.quantities.copy()\n    #how many largest and smaller elements we should remove from each end\n    removeLeft = removeRight = self.k\n    #where we\'ll start removing them\n    pointerLeft = 0\n    pointerRight = len(_list)-1\n```\n We keep going from left to right and from right to left until we\'ve removed k elements from both ends, and them we calculate the sum and the average\n```\nwhile removeLeft > 0:\n            leftmostKey = _list[pointerLeft]\n            if copy[leftmostKey] >= removeLeft:\n                copy[leftmostKey] -= removeLeft\n                removeLeft = 0\n            else:\n                removeLeft -= copy[leftmostKey]\n                copy[leftmostKey] = 0    \n            pointerLeft += 1\n        \n        while removeRight > 0:\n            rightmostKey = _list[pointerRight]\n            if copy[rightmostKey] >= removeRight:\n                copy[rightmostKey] -= removeRight\n                removeRight = 0\n            else:\n                removeRight -= copy[rightmostKey]\n                copy[rightmostKey] = 0\n            pointerRight -= 1\n    \n        total_sum = count = 0\n        for k in copy:\n            total_sum += k*copy[k]\n            count += copy[k]\n        return math.floor(total_sum/count)\n```\n\n# Complexity\n- Time complexity: $$O(n log n)$$\n    Overall complexity is dictated by sorting the unique elements of the queue using the map keys, so it becomes $$O(n log n)$$ where $$n$$ is the number of **unique** elements in the queue. \n\n- Space complexity:$$O(m)$$\n    $$m$$ is both the maximum size of the queue and the maximum size of the map if every element is unique (i.e.: there are no repeated elements)\n\n\n# Full Code\n```\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.queue = collections.deque()\n        self.count = 0\n        self.quantities = {}\n\n    def addElement(self, num: int) -> None:\n        if self.count >= self.m:\n            first = self.queue.popleft()\n            self.quantities[first] -= 1\n        else:\n            self.count += 1\n        self.queue.append(num)\n        self.quantities[num] = self.quantities[num] + 1 if num in self.quantities else 1\n\n\n        \n\n    def calculateMKAverage(self) -> int:\n        if self.count < self.m:\n            return -1\n        _list = sorted(self.quantities.keys())\n        copy = self.quantities.copy()\n        removeLeft = removeRight = self.k\n        pointerLeft = 0\n        pointerRight = len(_list)-1\n        while removeLeft > 0:\n            leftmostKey = _list[pointerLeft]\n            if copy[leftmostKey] >= removeLeft:\n                copy[leftmostKey] -= removeLeft\n                removeLeft = 0\n            else:\n                removeLeft -= copy[leftmostKey]\n                copy[leftmostKey] = 0    \n            pointerLeft += 1\n        \n        while removeRight > 0:\n            rightmostKey = _list[pointerRight]\n            if copy[rightmostKey] >= removeRight:\n                copy[rightmostKey] -= removeRight\n                removeRight = 0\n            else:\n                removeRight -= copy[rightmostKey]\n                copy[rightmostKey] = 0\n            pointerRight -= 1\n    \n        total_sum = count = 0\n        for k in copy:\n            total_sum += k*copy[k]\n            count += copy[k]\n        return math.floor(total_sum/count)\n```\nHope it was clear guys! bye
['Python3']