🔥🔥🔥 Python Simple Solution 🔥🔥🔥 | sliding window + sorted list | O(n log k) Time, O(k) Space
Intuition\ncount numbers in subarray and sort them by count and value.\nThen calculate the sum.\n\n# Solution 1 - brute force\nTime complexity: O(n k log k)\nSp
# Intuition\ncount numbers in subarray and sort them by count and value.\nThen calculate the sum.\n\n# Solution 1 - brute force\nTime complexity: $$O(n k log k)$$\nSpace complexity: $$O(k)$$ (not consider the answer space $$O(n$$))\n```python3 []\nclass Solution:\n    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:\n        res = []\n        for i in range(len(nums) - k + 1):\n            c = [[count, val] for val, count in Counter(nums[i:i + k]).items()]\n            c = heapq.nlargest(x, c)\n            res.append(sum(val * count for count, val in c))\n        return res\n```\n\n# Intuition\nUse sliding window.\nMaintain a number `total` and a set `in_top_x`.\ncheck if the number added in sliding window will be added in our top x.\nAlso need to check if the number removed or be squeezed out of top x.\n\n# Solution 2 - sliding window + sorted list\nTime complexity: $$O(n \\log k)$$\nSpace complexity: $$O(k)$$ (not consider the answer space $$O(n$$))\n```python3 []\nfrom sortedcontainers import SortedList\nclass Solution:\n    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:\n        res = []\n        counter = Counter(nums[:k - 1])\n        sl = SortedList(counter.keys(), key=lambda a: (-counter[a], -a))\n        total = 0\n        in_top_x = set()\n        for i in range(min(x, len(sl))):\n            total += sl[i] * counter[sl[i]]\n            in_top_x.add(sl[i])\n\n        for i in range(k - 1, len(nums)):\n            if nums[i] in sl:\n                sl.remove(nums[i])\n            counter[nums[i]] += 1\n            sl.add(nums[i])\n            j = sl.bisect_left(nums[i])\n            if j < x:\n                if nums[i] in in_top_x:\n                    total += nums[i]\n                else:\n                    total += nums[i] * counter[nums[i]]\n                    in_top_x.add(nums[i])\n            if len(sl) > x and sl[x] in in_top_x:\n                total -= sl[x] * counter[sl[x]]\n                in_top_x.remove(sl[x])\n\n            res.append(total)\n\n            sl.remove(nums[i - k + 1])\n            counter[nums[i - k + 1]] -= 1\n            sl.add(nums[i - k + 1])\n            j = sl.bisect_left(nums[i - k + 1])\n            if nums[i - k + 1] in in_top_x:\n                if j >= x:\n                    total -= nums[i - k + 1] * (counter[nums[i - k + 1]] + 1)\n                    in_top_x.remove(nums[i - k + 1])\n                else:\n                    total -= nums[i - k + 1]\n            if len(sl) >= x and sl[x - 1] not in in_top_x:\n                total += sl[x - 1] * counter[sl[x - 1]]\n                in_top_x.add(sl[x - 1])\n        return res\n```
['Python3']