2122. Recover the Original Array LeetCode Solution

In this guide, you will get 2122. Recover the Original Array LeetCode Solution with the best time and space complexity. The solution to Recover the Original Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Recover the Original Array solution in C++
Recover the Original Array solution in Java
Recover the Original Array solution in Python
Additional Resources

2122. Recover the Original Array LeetCode Solution image

Problem Statement of Recover the Original Array

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] <= 109
The test cases are generated such that there exists at least one valid array arr.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

2122. Recover the Original Array LeetCode Solution in C++

class Solution {
 public:
  vector<int> recoverArray(vector<int>& nums) {
    const int n = nums.size();
    unordered_map<int, int> count;

    for (const int num : nums)
      ++count[num];

    ranges::sort(nums);

    for (int i = 1; i < n; ++i) {
      const int x = nums[i] - nums[0];  // 2 * k
      if (x <= 0 || x % 2 == 1)
        continue;
      vector<int> arr = getArray(nums, x, count);
      if (!arr.empty())
        return arr;
    }

    throw;
  }

 private:
  vector<int> getArray(const vector<int>& nums, int x,
                       unordered_map<int, int> count) {
    vector<int> arr;
    for (const int num : nums) {
      if (const auto it = count.find(num);
          it == count.cend() || it->second == 0)
        continue;
      if (const auto it = count.find(num + x);
          it == count.cend() || it->second == 0)
        return {};
      --count[num];
      --count[num + x];
      arr.push_back(num + x / 2);
    }
    return arr;
  }
};
/* code provided by PROGIEZ */

2122. Recover the Original Array LeetCode Solution in Java

class Solution {
  public int[] recoverArray(int[] nums) {
    final int n = nums.length;
    Map<Integer, Integer> count = new HashMap<>();

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    Arrays.sort(nums);

    for (int i = 1; i < n; ++i) {
      final int x = nums[i] - nums[0]; // 2 * k
      if (x <= 0 || x % 2 == 1)
        continue;
      Map<Integer, Integer> countCopy = new HashMap<>();
      countCopy.putAll(count);
      int[] arr = getArray(nums, x, countCopy);
      if (arr.length == n / 2)
        return arr;
    }

    throw new IllegalarrrgumentException();
  }

  private int[] getArray(int[] nums, int x, Map<Integer, Integer> count) {
    List<Integer> arr = new ArrayList<>();
    for (final int num : nums) {
      if (count.getOrDefault(num, 0) == 0)
        continue;
      if (count.getOrDefault(num + x, 0) == 0)
        return new int[] {};
      count.merge(num, -1, Integer::sum);
      count.merge(num + x, -1, Integer::sum);
      arr.add(num + x / 2);
    }
    return arr.stream().mapToInt(Integer::intValue).toArray();
  }
}
// code provided by PROGIEZ

2122. Recover the Original Array LeetCode Solution in Python

class Solution:
  def recoverArray(self, nums: list[int]) -> list[int]:
    nums = sorted(nums)

    def getArray(x: int, count: collections.Counter) -> list[int]:
      arr = []
      for num in nums:
        if count[num] == 0:
          continue
        if count[num + x] == 0:
          return []
        count[num] -= 1
        count[num + x] -= 1
        arr.append(num + x // 2)
      return arr

    count = collections.Counter(nums)

    for i in range(1, len(nums)):
      x = nums[i] - nums[0]  # 2 * k
      if x <= 0 or x % 2 == 1:
        continue
      arr = getArray(x, count.copy())
      if arr:
        return arr
 # code by PROGIEZ