Python Counter: Use it to its fullest. 98ms, fastest solution yet... for slow python.
Intuition\n Describe your first thoughts on how to solve this problem. \nMany solutions here cleverly create a counter, and yet iterate through each num in the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMany solutions here cleverly create a counter, and yet iterate through each num in the full array to subtract matching pairs. We can do a little better though. Since we *have* the counter, we can iterate through that instead and remove whole chunks of matched sets in one step\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe same basic O(n^2) solution in most other posts, with a twist. Iterate through counter keys rather than the num array. Subtract counter vals to account for EVERY match of num and num + k in one step.\n\nIts a pretty minor optimization, but is neat and you may as well. \n\n\nOriginally I did try deleting key:val pairs in the dict so the dictionary actually gets smaller, and we can exit once its empty (knowing we have the right answer), but this is slower than just checking if the value in the dict == 0. \n\n# Complexity\nInstead of O(n^2), this is technically O(len(counter.keys())^2), though worst case that IS O(n^2). It improves the average and best case analysis though. \n\n\n# Code\n```\nfrom collections import Counter\n\n\nclass Solution:\n    def recoverArray(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        smallest, largest = nums[0], nums[-1]\n        nums_counter = Counter(nums)\n        knums = list(nums_counter.keys())\n\n        for knum in knums[1:]:\n            #technically this is 2k here, but thats less useful.\n            #Lets say K = 2k\n            K = knum - smallest\n            #We know smallest MUST be in the LOWER array, so smallest + K must exist or we have the wrong K. \n            # Same logic for largest. We can directly test this and maybe stop early\n            # This test accounts for hundreds of ms in runtime speedup\n            if K & 1 or smallest + K not in nums_counter or largest - K not in nums_counter:\n                continue\n            \n            #make new copies, dont recreate the counter each time. \n            ans = []\n            numsc = nums_counter.copy()\n                        \n            for num in knums:\n                #already accounted for all these\n                if numsc[num] == 0:\n                    continue\n                #Wrong K\n                if num + K not in numsc or numsc[num + K] == 0:\n                    break\n\n                #Update ALL matched pairs in one step                \n                count = min(numsc[num], numsc[num + K])        \n                numsc[num] -= count\n                numsc[num + K] -= count\n\n                # Need to add count many copies of our new num\n                ans += [num + K//2]*count\n       \n            if len(ans) == len(nums) // 2:\n                return ans                \n\n\n```
['Python3']