{x}
blog image

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:

  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.

Solution Explanation

This problem asks us to recover the original array arr given an array nums containing elements from lower and higher arrays. lower[i] = arr[i] - k and higher[i] = arr[i] + k, where k is an unknown positive integer.

The solution uses a brute-force approach with several optimizations. Here's a breakdown:

  1. Sorting: The input array nums is first sorted. This allows us to efficiently find pairs of numbers that could potentially represent lower[i] and higher[i] for some i.

  2. Iterating Through Potential k Values: The outer loop iterates through each element of nums (except the first) to check if the difference between it and the first element (nums[0]) can be a valid 2k. If the difference is not even or is 0, it's skipped because k must be a positive integer.

  3. Finding Pairs: For each potential 2k, a boolean array vis (or equivalent data structure in other languages) is used to track which elements of nums have been used. Two pointers l and r are employed to efficiently find pairs that differ by 2k. l starts at 1 (skipping the first element nums[0]). r starts from i+1 as nums[i] is already matched with nums[0]. The inner loop checks if the difference nums[r] - nums[l] is equal to 2k. If it's equal, it means we've found a pair (nums[l] and nums[r]) forming lower[i] and higher[i] for some i, and the corresponding element in the original array arr is calculated as (nums[l] + nums[r]) / 2.

  4. Validation: After finding a potential pair, the corresponding element in arr is added to the result list ans. The process continues until either all elements are used (the length of ans equals n, where 2n is the length of nums) or no more pairs are found.

  5. Returning the Result: If the length of ans becomes n/2, it means we have successfully reconstructed half of the original array using the found pairs. This array ans is returned. Otherwise, the loop continues checking for other potential k values. If no valid arr is found, an empty list is returned (or null in Java).

Time Complexity Analysis

The outer loop iterates up to O(n) times. The inner loop performs operations related to finding pairs of numbers that differ by 2k. In the worst case, this inner loop can also take O(n) time. Therefore, the overall time complexity is O(n^2). The sorting step contributes O(n log n), but this is dominated by the nested loops' O(n^2) complexity.

Space Complexity Analysis

The space complexity is dominated by the vis array (or its equivalent) which takes O(n) space. Other variables take constant space. Therefore, the space complexity is O(n).