Two Solutions Explained Python
Try all k\nTime: O(n^2)\n2 <= 2k <= max(nums) - min(nums)\nthe diff higher[i] - lower[i] == 2k, so even is important.\nsort the nums and try all differences num
**Try all k**\n**Time: O(n^2)**\n2 <= 2*k <= max(nums) - min(nums)\nthe diff higher[i] - lower[i] == 2*k, so even is important.\nsort the nums and try all differences nums[i] - nums[0].\nYou can check if a difference is valid in O(N) time. Just use two pointers (i, j). \ni is a pointer for elements in lower and j is a pointer for elements in higher.\nif nums[j] - nums[i] == diff then save the j pointer in a set.\nAt the end of iteration when (j == n) if the size of higher set == size of original array, then its a valid difference.\n\n```\ndef recoverArray(self, nums: List[int]) -> List[int]:\n    n = len(nums)\n    nums.sort()\n\n    def isValid(diff):\n        i = j = 0\n        higher = set()\n        while j < n:\n            while i in higher:\n                i += 1\n            if j == i:\n                j = i + 1\n                continue\n            if nums[j] - nums[i] == diff:\n                higher.add(j)\n                i += 1; j += 1\n            else: j += 1\n\n        if len(higher) == n//2:\n            return higher\n    \n    for i in range(1, n):\n        k = nums[i] - nums[0]\n        if k and not k%2:\n            higher = isValid(k)\n            if higher:\n                diff = k//2\n                return [nums[i] - diff for i in higher]\n    \n    return []\n```\n**Diff Counter** -- TLE\n**Time: O(n^2)**\nthe most common difference for each pair in nums, must be a valid difference value. There is no need to check its validity because question states that a valid answer must exist. \n```\ndef recoverArray(self, nums):\n    n = len(nums)\n    nums.sort()\n    \n    diffFreq = defaultdict(int)\n    max_freq = 0\n    for i in range(n):\n        for j in range(i+1, n):\n            diff = nums[j] - nums[i]\n            if diff and not(diff)%2:\n                diffFreq[diff] += 1\n\n                if diffFreq[diff] > max_freq:\n                    max_freq_diff = diff\n                    max_freq = diffFreq[diff]\n    \n    i = j = 0\n    higher = set()\n    while j < n:\n        while i in higher:\n            i += 1\n        if j == i:\n            j = i + 1\n            continue\n        if nums[j] - nums[i] == max_freq_diff:\n            higher.add(j)\n            i += 1; j += 1\n        else:\n            j += 1\n\n    max_freq_diff //= 2\n    return [nums[i] - max_freq_diff for i in higher]\n```\n\n\n
['Hash Table', 'Sorting', 'Python']