2122. Recover the Original Array

Problem Description

Alice had an initial array arr containing n positive integers. To create variability, she decided to generate two new arrays, lower and higher, each also containing n elements. She chose a positive integer k and subtracted k from each element in arr to form lower, and added k to each element in arr to form higher. Thus, lower[i] = arr[i] - k and higher[i] = arr[i] + k.

Unfortunately, Alice lost all three arrays arr, lower, and higher. She now only remembers a single array nums that contains all the elements of lower and higher mingled together without any indication as to which element belongs to which array. The task is to help Alice by reconstructing the original array arr.

The constraints are that nums consists of 2n integers with exactly n integers from lower and n from higher. We need to return any valid construction of arr. It is important to remember that multiple valid arrays might exist, so any of them will be considered correct. Furthermore, the problem guarantees that there is at least one valid array arr.

Intuition

Since the original array arr is lost, and the elements in nums cannot be directly distinguished as belonging to either lower or higher, we need to analyze the properties of numbers in lower and higher. Recognizing that each element in higher is generated by adding the same fixed value k to the respective elements in lower, we can sort nums to sequentially establish pairs of elements that could potentially correspond to the original and its modification by k.

The first step in uncovering arr is sorting nums. After the sort, knowing that the smallest value must be from the lower array and the next smallest that forms a valid pair must be from higher, one can attempt to determine the value of k. This value should be twice the chosen k because it's the difference between counterpart elements from higher and lower.

For each potential k (which is the difference between a pair of elements in nums), we check if it's even and not zero. Since k has to be a positive integer, this test eliminates invalid candidates.

Once a potential k is found, we proceed to form the pairs. A boolean array, vis, is used to track elements already used in pairs. If the right elements are not found for pairing, we know the current k candidate is invalid, and we move to the next candidate.

The pairing logic relies on finding elements nums[l] and nums[r] where nums[r] - nums[l] equals the difference d we're exploring as 2k. We keep appending the midpoint of these pairs (nums[l] + nums[r]) / 2 to the ans list until either we run out of elements or can no longer find valid pairs, which indicates a complete arr.

If a complete arr is found where the number of found pairs equals n, we return arr. If not, we continue testing other differences until a valid array is constructed or all possibilities have been exhausted, in which case an empty list is returned.

Learn more about Sorting patterns.

Solution Approach

The implementation of the solution involves a few key steps that utilize algorithms and data structures effectively to reconstruct Alice's initial array arr.

1. Sorting nums: The very first operation in the code is sorting the nums array. This is a common preprocessing step in many problems, as it often simplifies the problem by ordering the elements. In our case, sorting is essential because it allows us to pair elements in nums that could represent an original and its counterpart modified by k.

2. Finding the potential k: The for-loop starts with i at index 1, iterating through the sorted nums. Each iteration examines whether nums[i] - nums[0] is a potential 2k (the actual k multiplied by 2). Only even and non-zero differences are considered valid because we need a positive integer k.

3. Reconstructing arr: A boolean array vis is created to keep track of which elements have already been paired. Initially, it marks the element corresponding to the current candidate k (nums[i] at the top of the loop) as used. The code maintains two pointers, l and r, which start searching for pairs from the beginning of nums. These pointers skip used elements tracked by vis.

4. Pairing elements using two pointers: The paired elements are chosen by verifying that nums[r] - nums[l] equals d (the current candidate 2k). For each such pair, the midpoint (nums[l] + nums[r]) / 2, representing an element in arr, is calculated and appended to ans.

5. Handling edge cases and completing the array: The pairing process continues until it's no longer possible to pair elements according to the current d value. If a complete arr is reconstructed such that the number of pairs equals n (which is half the length of nums), then ans is returned as a valid original array.

6. Returning the result: If, during the pairing process, an inconsistency is found, the algorithm breaks out of the inner while loop, meaning the current d is not valid, and the for-loop continues with the next candidate. If the algorithm finds a correct sequence of pairs for ans, it is returned as a valid candidate. Otherwise, the pairing attempt will fail for all differences d, and the function will return an empty list, though this is guaranteed not to happen as per the problem statement.

The above approach takes advantage of sorted arrays, the two-pointer technique, and the boolean visitation array to implement an efficient and effective solution.

Example Walkthrough

Let's walk through the solution approach with a small example. Suppose Alice remembers the following mingled array nums that has elements from both lower and higher arrays: nums = [3, 9, 5, 7].

According to the problem description and solution approach, we want to reconstruct the original array arr. Follow these steps:

1. Sort nums: After sorting, the array nums becomes [3, 5, 7, 9]. Sorting ensures that the smallest element, which must be from the lower array, is at the beginning.

2. Finding potential k: Starting from the second smallest number in nums, which is 5, we take the difference with the smallest number 3, resulting in 2. Since the difference must be 2k (and k is a positive integer), valid potential k values are 1, the only number that when doubled gives 2.

3. Reconstructing arr: Initialize vis = [false, false, false, false] since no elements have been paired yet. We will look for pairs that have a difference of 2 (our potential 2k).

4. Pairing elements using two pointers:

   • We start with the first element 3 and look for an element that has a difference of 2. The next element is 5, and 5 - 3 = 2 which is our 2k. We mark elements 3 and 5 as visited: vis = [true, true, false, false].
   • Now, we calculate the midpoint, (3 + 5) / 2 = 4, which is a candidate for arr. Hence, arr = [4].
   • We continue to the next unvisited element which is 7, and look for its pair. We find 9 (9 - 7 = 2). Now vis = [true, true, true, true].
   • The midpoint of 7 and 9 is (7 + 9) / 2 = 8, which is added to arr. Now arr = [4, 8].

5. Completing the array: At this point, all elements in nums have been visited and paired correctly. There are two pairs, and this matches n (since nums is of length 2n and arr of length n). The process is complete, and we have successfully reconstructed arr.

6. Returning the result: The array arr = [4, 8] is returned as a valid construction of Alice's original array.

By following these steps, we have used the sorted array, the two-pointer technique, and a boolean array that tracks paired elements to effectively reconstruct the array arr that Alice had before the arrays were lost.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the algorithm can be analyzed as follows:

1. Sorting the nums array: Sorting an array of size n typically takes O(n log n) time.

2. The outer loop runs at most n times because it iterates through the sorted nums array starting from the second element.

3. For each element in the outer loop, there are two inner loops (while loops) that could potentially run n times each in the worst case.

   • The first inner loop increments l until it finds an unvisited element.
   • The second inner loop increments r until it finds the pair element that satisfies nums[r] - nums[l] == d.

However, each element from the nums array gets paired at most once due to the vis array tracking the visited status. This means that in total, each inner loop contributes at maximum n iterations across all iterations of the outer loop, not n per outer loop iteration.

Thus, the time complexity is primarily dictated by the outer loop and the pairing process, leading to a complexity of O(n log n) for sorting plus O(n) for pairing, which simplifies to O(n log n) for the entire algorithm.

Therefore, the overall time complexity of the code is O(n log n).

Space Complexity

The space complexity can be considered by analyzing the storage used by the algorithm:

1. The vis array: An array of size n used to keep track of the visited elements, which occupies O(n) space.

2. The ans array: Potentially, this array could store n/2 elements when all the correct pairings are made (since pairs are formed), so it uses O(n) space as well.

As such, the space complexity of the algorithm is determined by the additional arrays used for keeping track of visited elements and storing the answer, leading to O(n) space complexity.

In conclusion, the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.