#2122

Recover the Original Array

master · 1675 · lc hard +32 · verified · 41.3% accepted · 392 likes · top 22%

⚑ Frequency Counting

Description

Alice originally had a 0-indexed array arr of n positive integers. She chose a positive integer k and created two new arrays:

 - lower[i] = arr[i] - k for every index i where 0 <= i < n

 - higher[i] = arr[i] + k for every index i where 0 <= i < n

Alice lost all three arrays, but she remembers which integers appeared in lower and higher (though not which integer belonged to which array).

Given a combined array nums of 2n integers — exactly n from lower and n from higher — recover and return the original array arr. If multiple valid arrays exist, return any of them.

Note: Test cases guarantee at least one valid arr exists.

Example 1:

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12].

Example 2:

Input: nums = [1,1,3,3]
Output: [2,2]
Explanation:
If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3].
Combining lower and higher gives us [1,1,3,3], which is equal to nums.
Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0.
This is invalid since k must be positive.

Example 3:

Input: nums = [5,435]
Output: [220]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

Code

1
2
3