1
class Solution(object):
2
    def recoverArray(self, nums):
3
        nums.sort()
4
        mid = len(nums) // 2
5
        # All possible k are (nums[j] - nums[0]) // 2, otherwise there is no num that satisfies nums[0] + k = num - k.
6
        # For nums is sorted, so that any 2 elements (x, y) in nums[1:j] cannot satisfy x + k = y - k.
7
        # In other words, for any x in nums[1:j], it needs to find y from nums[j + 1:] to satisfy x + k = y - k, but
8
        # unfortunately if j > mid, then len(nums[j + 1:]) < mid <= len(nums[1:j]), nums[j + 1:] are not enough.
9
        # The conclusion is j <= mid.
10
        # If you think it’s not easy to understand why mid is enough, len(nums) can also work well
11
        # for j in range(1, len(nums)):
12
        for j in range(1, mid + 1):  # O(N)
13
            if (
14
                nums[j] - nums[0] > 0 and (nums[j] - nums[0]) % 2 == 0
15
            ):  # Note the problem described k is positive.
16
                k, counter, ans = (
17
                    (nums[j] - nums[0]) // 2,
18
                    collections.Counter(nums),
19
                    [],
20
                )
21
                # For each number in lower, we try to find the corresponding number from higher list.
22
                # Because nums is sorted, current n is always the current lowest num which can only come from lower
23
                # list, so we search the corresponding number of n which equals to n + 2 * k in the left
24
                # if it can not be found, change another k and continue to try.
25
                for (
26
                    n
27
                ) in (
28
                    nums
29
                ):  # check if n + 2 * k available as corresponding number in higher list of n
30
                    if (
31
                        counter[n] == 0
32
                    ):  # removed by previous num as its corresponding number in higher list
33
                        continue
34
                    if (
35
                        counter[n + 2 * k] == 0
36
                    ):  # not found corresponding number in higher list
37
                        break
38
                    ans.append(n + k)
39
                    counter[n] -= 1  # remove n
40
                    counter[
41
                        n + 2 * k
42
                    ] -= 1  # remove the corresponding number in higher list
43
                if len(ans) == mid:
44
                    return ans