Problem Description

You are given an array called changed that was created through a specific transformation process. The original process worked like this:

1. Start with an integer array called original
2. For every element in original, append twice its value to create a new array
3. Randomly shuffle this new array to get changed

For example, if original = [1, 3, 4], then after doubling we get [1, 3, 4, 2, 6, 8], which after shuffling might become changed = [6, 3, 8, 1, 4, 2].

Your task is to determine if the given array changed could have been created through this process. If it was, return the original array (elements can be in any order). If changed could not have been created this way, return an empty array.

The key insight is that every element x in the original array must have both x and 2x present in the changed array. The solution sorts the array and greedily pairs each element with its double. Starting from the smallest element ensures we correctly identify which elements belong to the original array versus which are the doubled values.

The algorithm uses a counter to track available elements. For each element x, it checks if x is still available (hasn't been paired yet), then tries to pair it with 2x. If 2x isn't available, the array cannot be a valid doubled array. The bit shift operation x << 1 is used as an efficient way to calculate 2x.

Intuition

The key observation is that if we have a valid doubled array, the smallest element in changed must belong to the original array. Why? Because the smallest element cannot be a doubled value of any other element in the array (since doubling makes numbers larger, not smaller).

Once we identify that the smallest element belongs to original, we know its double (2 * smallest) must also exist somewhere in changed. We can pair these two elements and remove them from consideration.

This suggests a greedy approach: always process elements from smallest to largest. For each unprocessed element x, we know it must be from the original array (since all smaller elements have already been processed and paired). We then look for its double 2x to pair with it.

Why does sorting help? Without sorting, we might mistakenly treat a doubled value as an original element. For instance, if changed = [4, 2, 8, 1], we might wrongly think 4 is an original element and look for 8 as its double. But actually, 4 is the double of 2. By sorting to get [1, 2, 4, 8] and processing from left to right, we correctly identify 1 and 2 as original elements with doubles 2 and 4 respectively.

The counting approach with a hash table allows us to efficiently track which elements are still available for pairing. When we use an element as either an original or a double, we decrement its count. If at any point we need an element that's not available (count is 0), we know the array cannot be a valid doubled array.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows these steps:

1. Sort the array: First, we sort the changed array in ascending order. This ensures we process elements from smallest to largest, allowing us to correctly identify which elements belong to the original array.

2. Count element frequencies: We use a Counter (hash table) to track the frequency of each element in the sorted array. This data structure allows us to efficiently check availability and update counts as we pair elements.

3. Iterate and pair elements: We traverse through the sorted array. For each element x:

   • Check if cnt[x] > 0. If it's 0, this element has already been used as someone's double, so we skip it with continue.
   • Decrement cnt[x] by 1 to mark that we're using this element as an original value.
   • Check if cnt[x << 1] > 0 (where x << 1 is equivalent to x * 2). If the double doesn't exist or has already been fully used, we return an empty array as this isn't a valid doubled array.
   • Decrement cnt[x << 1] by 1 to mark that we've paired this double with its original.
   • Add x to our answer array since we've confirmed it's part of the original array.

4. Return the result: After successfully processing all elements, we return the answer array containing the original elements.

The algorithm has a time complexity of O(n log n) due to sorting, where n is the length of the changed array. The space complexity is O(n) for the counter and answer array.

The bit shift operation x << 1 is used as an optimization for multiplying by 2, as left-shifting by 1 bit position doubles the value in binary representation.

Example Walkthrough

Let's walk through the solution with changed = [6, 3, 8, 1, 4, 2].

Step 1: Sort the array After sorting: [1, 2, 3, 4, 6, 8]

Step 2: Create frequency counter

cnt = {1: 1, 2: 1, 3: 1, 4: 1, 6: 1, 8: 1}

Step 3: Process each element from smallest to largest

Processing 1:

• Check if cnt[1] > 0? Yes (count is 1)
• Mark 1 as used: cnt[1] = 0
• Look for its double: 1 << 1 = 2
• Check if cnt[2] > 0? Yes (count is 1)
• Mark 2 as paired: cnt[2] = 0
• Add 1 to answer: answer = [1]
• Updated counter: cnt = {1: 0, 2: 0, 3: 1, 4: 1, 6: 1, 8: 1}

Processing 2:

• Check if cnt[2] > 0? No (already used as 1's double)
• Skip with continue

Processing 3:

• Check if cnt[3] > 0? Yes (count is 1)
• Mark 3 as used: cnt[3] = 0
• Look for its double: 3 << 1 = 6
• Check if cnt[6] > 0? Yes (count is 1)
• Mark 6 as paired: cnt[6] = 0
• Add 3 to answer: answer = [1, 3]
• Updated counter: cnt = {1: 0, 2: 0, 3: 0, 4: 1, 6: 0, 8: 1}

Processing 4:

• Check if cnt[4] > 0? Yes (count is 1)
• Mark 4 as used: cnt[4] = 0
• Look for its double: 4 << 1 = 8
• Check if cnt[8] > 0? Yes (count is 1)
• Mark 8 as paired: cnt[8] = 0
• Add 4 to answer: answer = [1, 3, 4]
• Updated counter: cnt = {1: 0, 2: 0, 3: 0, 4: 0, 6: 0, 8: 0}

Processing 6:

• Check if cnt[6] > 0? No (already used as 3's double)
• Skip with continue

Processing 8:

• Check if cnt[8] > 0? No (already used as 4's double)
• Skip with continue

Step 4: Return result Return [1, 3, 4] - successfully reconstructed the original array!

The key insight: by processing smallest to largest, we correctly identify that 1, 3, and 4 are original elements (with doubles 2, 6, and 8 respectively), rather than mistakenly treating doubled values as originals.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the length of the array changed.

The time complexity is dominated by the sorting operation changed.sort(), which takes O(n × log n) time. After sorting, the code iterates through the array once with a for loop, performing constant-time operations for each element (Counter lookups and updates are O(1) on average). The Counter initialization takes O(n) time. Therefore, the overall time complexity is O(n × log n) + O(n) + O(n) = O(n × log n).

Space Complexity: O(n), where n is the length of the array changed.

The space complexity is determined by:

• The Counter object cnt which stores at most n key-value pairs: O(n)
• The answer list ans which can contain at most n/2 elements: O(n)
• The sorting operation may use O(log n) space for the recursion stack (if using an in-place sorting algorithm like quicksort) or O(n) space (if using mergesort)

The dominant space usage is O(n), resulting in an overall space complexity of O(n).

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

Common Pitfalls

1. Incorrect Handling of Zero Values

The most critical pitfall in this solution is the incorrect handling of zeros. When the original array contains 0, its double is also 0 (since 0 × 2 = 0). This means each zero in the original array requires TWO zeros in the changed array.

Problem Example:

• Input: changed = [0, 0, 0, 0]
• Expected: original = [0, 0] (two zeros doubled gives four zeros)
• Buggy behavior: The algorithm tries to pair each 0 with itself as its double, potentially returning [0, 0, 0, 0] as the original array

Solution: Add special handling for zeros:

for number in changed:
    if frequency_counter[number] == 0:
        continue
  
    frequency_counter[number] -= 1
    doubled_value = number * 2
  
    # Special case: when number is 0, we need another 0 available
    # (not the same one we just decremented)
    if frequency_counter[doubled_value] <= 0:
        return []
  
    frequency_counter[doubled_value] -= 1
    original_array.append(number)

2. Odd Length Array Check

If the input array has an odd number of elements, it cannot be a valid doubled array since the doubled array must have exactly twice the number of elements as the original.

Solution: Add a length check at the beginning:

def findOriginalArray(self, changed: List[int]) -> List[int]:
    # Early return for odd-length arrays
    if len(changed) % 2 != 0:
        return []
  
    # Rest of the implementation...

3. Negative Numbers Handling

While the problem typically involves non-negative integers, if negative numbers are allowed, the sorting and pairing logic becomes more complex. For negative numbers, their doubles are "more negative" (e.g., -3 doubled is -6).

Solution: Sort by absolute value if negatives are allowed:

# Sort by absolute value for correct pairing with negatives
changed.sort(key=abs)

4. Integer Overflow with Bit Shifting

While x << 1 is efficient, it can cause issues with very large numbers near the integer limit. Using x * 2 is safer and more readable.

Complete Corrected Solution:

def findOriginalArray(self, changed: List[int]) -> List[int]:
    # Check for odd length
    if len(changed) % 2 != 0:
        return []
  
    changed.sort()
    frequency_counter = Counter(changed)
    original_array = []
  
    for number in changed:
        if frequency_counter[number] == 0:
            continue
      
        frequency_counter[number] -= 1
        doubled_value = number * 2
      
        if frequency_counter[doubled_value] <= 0:
            return []
      
        frequency_counter[doubled_value] -= 1
        original_array.append(number)
  
    return original_array