Formatted question description: https://leetcode.ca/all/2122.html

# 2122. Recover the Original Array (Hard)

Alice had a **0-indexed** array `arr`

consisting of `n`

**positive** integers. She chose an arbitrary **positive integer** `k`

and created two new **0-indexed** integer arrays `lower`

and `higher`

in the following manner:

`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`

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays `lower`

and `higher`

, but not the array each integer belonged to. Help Alice and recover the original array.

Given an array `nums`

consisting of `2n`

integers, where **exactly** `n`

of the integers were present in `lower`

and the remaining in `higher`

, return *the original array*

`arr`

. In case the answer is not unique, return *.*

**any**valid array**Note:** The test cases are generated such that there exists **at least one** valid array `arr`

.

**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].

**Constraints:**

`2 * n == nums.length`

`1 <= n <= 1000`

`1 <= nums[i] <= 10`

^{9}- The test cases are generated such that there exists
**at least one**valid array`arr`

.

**Companies**:

Google

**Related Topics**:

Array, Hash Table, Sorting, Enumeration

**Similar Questions**:

## Solution 1.

First sort the array.

The idea is to simply use `A[0]`

as the smallest element in `lower`

and try each `A[i] (1 <= i <= N)`

as the corresponding element in `higher`

.

But the implementation can easily get TLE. We need to use tricks to speed it up.

- We might many duplicate
`k`

s. Use set to dedup them. - To further narrow down, we use
`A.back()`

as the largest element in`higher`

and try each`A[i] (N-1 <= i < A.size()-1)`

as the corresponding element in`lower`

.

```
// OJ: https://leetcode.com/problems/recover-the-original-array/
// Time: O(N^2 * logN)
// Space: O(N)
class Solution {
public:
vector<int> recoverArray(vector<int>& A) {
sort(begin(A), end(A));
int N = A.size() / 2;
unordered_set<int> ks, ks2; // Dedup `k`s using set.
for (int i = 1; i <= N; ++i) { // Generate possible `k`s: Use A[0] as the smallest element in lower. Try each A[i] (1 <= i <= N) as the corresponding element in higher.
int d = A[i] - A[0];
if (d && d % 2 == 0) ks.insert(d / 2);
}
for (int i = N - 1; i < A.size() - 1; ++i) { // Narrow down: Use A.back() as the largest element in higher. Try each A[i] (N-1 <= i < A.size()-1) as the corresponding element in lower.
int d = A.back() - A[i];
if (d % 2 == 0 && ks.count(d / 2)) ks2.insert(d / 2);
}
vector<int> ans;
ans.reserve(N);
for (int k : ks2) {
multiset<int> s(begin(A), end(A));
ans.clear();
while (s.size()) {
int a = *s.begin();
s.erase(s.begin());
auto it = s.find(a + 2 * k);
if (it == s.end()) break;
s.erase(it);
ans.push_back(a + k);
}
if (s.empty()) return ans;
}
return {};
}
};
```

## Solution 2.

```
// OJ: https://leetcode.com/problems/recover-the-original-array/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
vector<int> recoverArray(vector<int>& A) {
sort(begin(A), end(A));
int N = A.size() / 2;
vector<int> ans;
ans.reserve(N);
for (int i = 1; i <= N + 1; ++i) {
int k = A[i] - A[0];
if (k == 0 || k % 2) continue;
k /= 2;
ans.clear();
int pos = 0;
for (int j = 0; j < A.size(); ++j) {
if (pos == ans.size()) ans.push_back(A[j] + k);
else {
int d = A[j] - ans[pos];
if (d == k) ++pos;
else if (d < k) ans.push_back(A[j] + k);
else break;
}
}
if (pos == N) return ans;
}
return {};
}
};
```