2007. Find Original Array From Doubled Array

Problem Description

This problem provides an array called changed, which has been created by taking an original array of integers, doubling each element, appending these doubled numbers to the original array, and then shuffling the entire collection of numbers.

Our task is to reconstruct the original array from the changed array. However, there are some constraints:

1. If the changed array has an odd number of elements, it's impossible to obtain the original array since doubling each element of the original array and then merging would result in an even number of total elements.
2. For each element in the original array, there must be a corresponding element in changed that is double its value.
3. If changed does not satisfy the property of being a "doubled array,” as described, we need to return an empty array.

We are allowed to return the elements of the original array in any order, adding flexibility to our solution.

Intuition

To find the solution, the following intuition can guide us:

1. Sorting: We start by sorting changed since this will arrange all double elements after their corresponding originals (since 2 * x > x for all x > 0). Sorting also helps us to handle duplicates effectively.

2. Counting: Using a counter (frequency map) over the sorted changed array helps in keeping track of the elements we've used for forming the original array and the elements that need to be paired with their doubles.

3. Pairing and Elimination: We iterate over the sorted changed array and look for the double of each element. If for any element x, the element 2x does not exist in sufficient quantity (or does not exist at all), we cannot form the original array, hence, we return an empty array.

4. Building the Original Array: If an element x and its double 2x are found, we pair them and reduce their count in the frequency map. The element x is added to the original array.

5. Validation: In the end, if the generated original array has exactly half the length of the changed array, we have successfully reformed the original array. Otherwise, the changed array wasn't a doubled array, to begin with, or we couldn't pair all elements correctly, and we return an empty array.

Using this approach caters to all conditions provided in the problem, thus guaranteeing a correct solution when one is possible.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows the intuition closely using Python's built-in data structures and sorting algorithm.

Here's the step-by-step breakdown of the solution approach:

1. Check for the Odd Number of Elements: A quick check to confirm if the length of the changed array is odd. Since the doubled array should be even in length, return an empty array immediately if this is the case.

   1n = len(changed)
   2if n & 1:
   3    return []

2. Use a Counter for Frequency Tracking: A Counter object from the collections module is utilized to keep a frequency map of the elements in changed.

   1cnt = Counter(changed)

3. Sort the changed Array: The changed array is sorted to ensure that the elements and their doubles are aligned in increasing order.

   1changed.sort()

4. Iterate to Build the original Array: A for-loop iterates over each element in the sorted changed array, applying the following logic:

   • Skip Processed Elements: If an element x has already been used (i.e., its count is 0), skip it.

     1if cnt[x] == 0:
     2    continue

   • Check for Double's Existence: If there is not enough of the double of x remaining (i.e., cnt[2 * x] is 0 or negative), the changed cannot be a doubled array, so return an empty list.

     1if cnt[x * 2] <= 0:
     2    return []

   • Add Element to original and Update Counts: If a valid double is found, append x to the original array and decrement the counts for x and 2 * x.

     1ans.append(x)
     2cnt[x] -= 1
     3cnt[x * 2] -= 1

5. Final Validation and Return: After the loop is done, check if the length of the original array is exactly half the changed array (which implies each element was paired correctly). If not, the changed array couldn't have been a doubled array, and thus, return an empty array.

   1return ans if len(ans) == n // 2 else []

By utilizing a sorted array and a frequency map, the algorithm ensures that all elements can be paired with their corresponding doubles, maintaining linearithmic time complexity due to sorting, with the remainder of operations being linear within the sorted array. The space complexity is linear due to the extra space used for the Counter and the resulting original array.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following changed array:

1changed = [1, 3, 4, 2, 6, 8]

Step-by-step, we perform the following actions:

1. Check for Odd Number of Elements: The length of the changed array is 6, which is even. We can proceed.

2. Use a Counter for Frequency Tracking: Generate a frequency map:

   1cnt = Counter([1, 3, 4, 2, 6, 8]) # Counter({1: 1, 3: 1, 2: 1, 4: 1, 6: 1, 8: 1})

3. Sort the changed Array: The sorted changed array looks like this:

   1changed = [1, 2, 3, 4, 6, 8]

4. Iterate to Build the original Array:

   • For the first element 1, we find that its double 2 exists, so we add 1 to original and update the counts:

     1ans = [1]
     2cnt = {1: 0, 3: 1, 2: 0, 4: 1, 6: 1, 8: 1}

   • We skip 2 since its count is now 0.

   • Next, for 3, we find its double 6, add 3 to original, and update counts:

     1ans = [1, 3]
     2cnt = {1: 0, 3: 0, 2: 0, 4: 1, 6: 0, 8: 1}

   • We skip 4 as we don't have 8 (double of 4) in enough quantity (count is 0), and since we can't find a valid double, we would normally return an empty array. However, for demonstration purposes, we will assume the double 8 exists and continue:

     1ans = [1, 3, 4]
     2cnt = {1: 0, 3: 0, 2: 0, 4: 0, 6: 0, 8: 0}

5. Final Validation and Return: Now ans has 3 elements, which is half of the changed array's length. Therefore, assuming that a double for each element existed, our original array is [1, 3, 4].

This simplified example demonstrates how each step logically brings us closer to the reconstructed original array or leads us to conclude that reconstruction is not possible if the conditions are not met.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be broken down as follows:

1. Getting the length of changed (n = len(changed)) is an O(1) operation.
2. Checking for even length (if n & 1) is also an O(1) operation.
3. Creating a counter (cnt = Counter(changed)) counts the frequency of each number in changed, which is an O(n) operation.
4. Sorting the array (changed.sort()) takes O(n log n) time.
5. The loop runs through the sorted list of numbers (for x in changed). In the worst case, it runs n times. Each operation inside is O(1) because accessing and modifying the counter is constant time, given a good hash function.
6. Condition checks inside the loop and counter updates are all O(1).
7. The last return statement (return ans if len(ans) == n // 2 else []) is an O(1) operation.

The most time-consuming steps are the counter creation and the sorting. Adding the complexities, we get:

O(n) (for counting) + O(n log n) (for sorting) + O(n) (for iterating through the list) = O(n log n).

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

Space Complexity

For space complexity:

1. Additional space is used to store the counter (cnt), which can be up to O(n) if all numbers are unique.
2. Space for the output array (ans), which is half of the input array's size in the best case, so O(n/2) simplifies to O(n).

Hence, the overall space complexity of the algorithm is O(n).

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