# Recover the Original Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/recover-the-original-array)
Canonical: https://scaleengineer.com/dsa/problems/recover-the-original-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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:

1. `lower[i] = arr[i] - k`, for every index `i` where `0 <= i < n`
2. `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] <= 109`
* The test cases are generated such that there exists **at least one** valid array `arr`.

# Approaches
## Exponential Brute Force Partitioning
This approach explores all possible ways to partition the `2n` numbers into a `lower` array and a `higher` array, each of size `n`. For each partition, it checks if it could have been generated from some original array `arr` and a positive integer `k`.
**Time:** O(C(2n, n) * n log n)
Generating all partitions takes `C(2n, n)` time. For each partition, we perform sorting, which takes `O(n log n)`, and a linear scan, which takes `O(n)`. The sorting step dominates the work done per partition. This complexity is exponential and thus not feasible. · **Space:** O(n)
This space is required to store a single partition (both `lower` and `higher` candidate arrays) during processing.
**Pros:** It's a direct, brute-force interpretation of the problem definition.; It is guaranteed to find a valid solution.
**Cons:** Extremely inefficient due to its exponential time complexity.; The number of partitions grows astronomically with `n`, making it infeasible for the given constraints (e.g., for `n=15`, `2n=30`, `C(30, 15)` is over 155 million).
### Explanation
The most straightforward, yet impractical, way to solve the problem is to try every possible assignment of the `2n` numbers in `nums` to either the `lower` set or the `higher` set. The number of ways to choose `n` elements for the `lower` set from `2n` elements is given by the binomial coefficient "2n choose n" (`C(2n, n)`).

The algorithm would recursively generate all subsets of `nums` of size `n`. Each such subset is a candidate for the `lower` array. The remaining `n` elements would form the `higher` array.

For each candidate partition (`lower_candidate`, `higher_candidate`):
1.  Sort both `lower_candidate` and `higher_candidate` arrays.
2.  Calculate the difference `d = higher_candidate[0] - lower_candidate[0]`.
3.  Check if this difference `d` is positive and consistent for all other pairs of elements. That is, check if `higher_candidate[i] - lower_candidate[i] == d` for all `i` from `1` to `n-1`.
4.  If the difference is consistent and positive, we have found a valid `2k = d`. The original array `arr` can be reconstructed as `arr[i] = lower_candidate[i] + k = lower_candidate[i] + d/2`. Since a solution is guaranteed to exist, we can return this `arr`.

This method is too slow for the given constraints but represents a foundational brute-force solution.
### Algorithm
- Generate all possible subsets of `nums` that have a size of `n`. Each such subset is a candidate for the `lower` array.
- For each candidate `lower` array, the remaining `n` elements of `nums` form the candidate `higher` array.
- Sort both the candidate `lower` and `higher` arrays.
- Calculate the difference `d = higher[0] - lower[0]`.
- If `d` is not a positive value, this partition is invalid, so we discard it and move to the next one.
- Check if this difference `d` is consistent for all pairs of elements, i.e., `higher[i] - lower[i] == d` for all `i`.
- If the difference is consistent, we have found a valid `2k = d`. The original array `arr` can be reconstructed as `arr[i] = lower[i] + k` (where `k = d / 2`).
- Since a solution is guaranteed to exist, this process will eventually find it, and we can return the reconstructed `arr`.

## Optimized Approach with Sorting
This approach significantly improves upon the naive brute force by using a key insight: after sorting the `nums` array, the smallest element `nums[0]` must belong to the `lower` array. This reduces the search space for `k` dramatically. We can iterate through possible partners for `nums[0]`, which gives us a candidate for `k`, and then efficiently verify this `k` for the entire array in linear time.
**Time:** O(n^2)
Sorting the `nums` array takes `O(n log n)`. The main part of the algorithm is the outer loop that iterates up to `2n-1` times (`O(n)`) to select a candidate `k`. Inside this loop, the `check` function is called. This function builds a frequency map (`O(n)`) and then iterates through `nums` again (`O(n)`), performing constant-time hash map operations on average. So, the verification step is `O(n)`. The total complexity is `O(n log n) + O(n) * O(n) = O(n^2)`. · **Space:** O(n)
The frequency map used for verification can store up to `2n` distinct numbers in the worst case. The result list also requires `O(n)` space. Thus, the space complexity is `O(n)`.
**Pros:** Vastly more efficient than the naive exponential approach.; Correct and guaranteed to find the solution under the problem's constraints.; The logic is straightforward and relatively simple to implement.
**Cons:** The `O(n^2)` time complexity might be a concern for significantly larger constraints, although it is efficient enough for the given problem constraints (`n <= 1000`).
### Explanation
The algorithm begins by sorting the `nums` array. This is a critical step because it establishes that `nums[0]` must be a `lower` value, say `arr[i] - k`. If it were a `higher` value, `arr[j] + k`, then its corresponding `lower` value, `arr[j] - k`, would be smaller, which contradicts `nums[0]` being the minimum element in the array.

The partner for `nums[0]` is `nums[0] + 2k`. This partner must be one of the other elements in the array, say `nums[j]` for some `j > 0`. We can iterate through `j` from `1` to `2n-1` to test each `nums[j]` as a potential partner.

For each `j`, we calculate a potential difference `diff = nums[j] - nums[0]`. This `diff` would be equal to `2k`. For `k` to be a positive integer, `diff` must be positive and even. If not, we discard this `j` and move to the next.

If `diff` is valid, we have a candidate `k = diff / 2`. We must now verify if this `k` can explain the entire `nums` array. This verification can be done efficiently in `O(n)` time. We use a frequency map (like a `HashMap`) to store the counts of each number in `nums`. We then iterate through the sorted `nums` array. For each number `num`, if its count is positive, we treat it as a `lower` value. We find its potential `higher` partner `num + 2k`. If this partner also exists in the map with a positive count, we've found a valid pair. We decrement the counts of both `num` and its partner in the map and add the original value `num + k` to our result array.

If at any point we cannot find a partner for a number, the candidate `k` is incorrect. We stop and try the next `j`. Since the problem guarantees a solution exists, this process will find one.

```java
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] recoverArray(int[] nums) {
        int n = nums.length / 2;
        Arrays.sort(nums);

        for (int j = 1; j < nums.length; j++) {
            int diff = nums[j] - nums[0];
            if (diff <= 0 || diff % 2 != 0) {
                continue;
            }
            
            int k = diff / 2;
            int[] result = check(nums, k, n);
            if (result.length == n) {
                return result;
            }
        }
        return new int[0]; // Should not be reached given the problem constraints
    }

    private int[] check(int[] nums, int k, int n) {
        List<Integer> resList = new ArrayList<>();
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (freq.get(num) == 0) {
                continue;
            }
            
            freq.put(num, freq.get(num) - 1);
            int partner = num + 2 * k;
            
            if (freq.getOrDefault(partner, 0) > 0) {
                freq.put(partner, freq.get(partner) - 1);
                resList.add(num + k);
            } else {
                return new int[0]; // Invalid k, this partition is not possible
            }
        }

        // This check is technically redundant if the above loop completes successfully
        // for a valid k, as resList will always have n elements.
        if (resList.size() == n) {
            int[] resultArr = new int[n];
            for (int i = 0; i < n; i++) {
                resultArr[i] = resList.get(i);
            }
            return resultArr;
        }
        return new int[0];
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. The smallest element, `nums[0]`, must be a `lower` element. Its corresponding `higher` element is `nums[0] + 2k`.
3. Iterate with an index `j` from `1` to `2n-1`. Each `nums[j]` is a candidate for being the partner of `nums[0]`.
4. For each `j`, calculate the potential difference `diff = nums[j] - nums[0]`.
5. If `diff` is zero, negative, or odd, it cannot represent `2k` (since `k` must be a positive integer). Continue to the next `j`.
6. If `diff` is valid, we have a candidate `k = diff / 2`. We must now verify if this `k` can form `n` pairs `(x, x + 2k)` from the numbers in `nums`.
7. To verify `k`, use a frequency map (e.g., a `HashMap`) to store the counts of each number in `nums`.
8. Iterate through the sorted `nums` array. For each `num`:
    a. If its count in the map is zero, it has already been used as a partner, so skip it.
    b. Otherwise, treat `num` as a `lower` element. Decrement its count in the map.
    c. Find its required partner `p = num + 2k`.
    d. Check if `p` exists in the map with a positive count. If yes, decrement `p`'s count and add the original value `num + k` to our result array.
    e. If `p` does not exist in the map with a positive count, this candidate `k` is incorrect. Abort the verification for this `k` and try the next `j`.
9. If the verification process completes and we have formed an array of size `n`, we have found a valid solution. Return it.

# Solutions
### Java

```java
class Solution {
public
  int[] recoverArray(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1, n = nums.length; i < n; ++i) {
      int d = nums[i] - nums[0];
      if (d == 0 || d % 2 == 1) {
        continue;
      }
      boolean[] vis = new boolean[n];
      vis[i] = true;
      List<Integer> t = new ArrayList<>();
      t.add((nums[0] + nums[i]) >> 1);
      for (int l = 1, r = i + 1; r < n; ++l, ++r) {
        while (l < n && vis[l]) {
          ++l;
        }
        while (r < n && nums[r] - nums[l] < d) {
          ++r;
        }
        if (r == n || nums[r] - nums[l] > d) {
          break;
        }
        vis[r] = true;
        t.add((nums[l] + nums[r]) >> 1);
      }
      if (t.size() == (n >> 1)) {
        int[] ans = new int[t.size()];
        int idx = 0;
        for (int e : t) {
          ans[idx++] = e;
        }
        return ans;
      }
    }
    return null;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> recoverArray(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    for (int i = 1, n = nums.size(); i < n; ++i) {
      int d = nums[i] - nums[0];
      if (d == 0 || d % 2 == 1)
        continue;
      vector<bool> vis(n);
      vis[i] = true;
      vector<int> ans;
      ans.push_back((nums[0] + nums[i]) >> 1);
      for (int l = 1, r = i + 1; r < n; ++l, ++r) {
        while (l < n && vis[l])
          ++l;
        while (r < n && nums[r] - nums[l] < d)
          ++r;
        if (r == n || nums[r] - nums[l] > d)
          break;
        vis[r] = true;
        ans.push_back((nums[l] + nums[r]) >> 1);
      }
      if (ans.size() == (n >> 1))
        return ans;
    }
    return {};
  }
};

```

### Python

```python
class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]: nums . sort() n = len(nums) for i in range(1, n): d = nums[i] - nums[0] if d == 0 or d % 2 == 1: continue vis = [False] * n vis[i] = True ans = [(nums[0] + nums[i]) >> 1] l, r = 1, i + 1 while r < n: while l < n and vis[l]: l += 1 while r < n and nums[r] - nums[l] < d: r += 1 if r == n or nums[r] - nums[l] > d: break vis[r] = True ans . append((nums[l] + nums[r]) >> 1) l, r = l + 1, r + 1 if len(ans) == (n >> 1): return ans return []

```