We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Original Array From Doubled Array

Number: 2117

Difficulty: Medium

Paid? No

Companies: Google, Microsoft

Problem Description

Given an array "changed" that is claimed to be created by taking an original array, appending twice each of its elements, and shuffling the resulting array, determine the original array. If "changed" is not a valid doubled array, return an empty array.

Key Insights

  • The length of "changed" must be even since it consists of the original array and its doubled counterpart.
  • Sorting the array helps to process elements in increasing order so that if an element x exists, then its pair 2*x can be looked up.
  • Use frequency counting (hash table) to match each x with its doubled value 2*x.
  • Special care is needed for zeros because 0 doubled is still 0.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of the array. Space Complexity: O(n) for the hash table storing frequency counts and the result array.

Solution

We first check if the "changed" array has an even number of elements, returning an empty array if not. Then, we sort the array and build a frequency dictionary. For each number in sorted order, if it appears in the dictionary, its corresponding doubled value must also appear sufficiently. If not, the array is not a valid doubled array. Otherwise, we add the original elements to our result and decrement the frequency for the doubled values accordingly. Special care must be taken for the case when the number is 0 since its pair is also 0.

Code Solutions

def find_original_array(changed):
    # Check if the length of changed is odd
    if len(changed) % 2 != 0:
        return []
    
    # Sort the array for processing the smallest numbers first
    changed.sort()
    frequency = {}
    
    # Build frequency dictionary
    for num in changed:
        frequency[num] = frequency.get(num, 0) + 1
    
    original = []
    
    # Iterate over the sorted numbers
    for num in changed:
        if frequency[num] == 0:
            # Skip if this number has already been used completely
            continue
        
        # For a valid doubled array, there must be a double for this number
        double = num * 2
        if frequency.get(double, 0) <= 0:
            # If not enough doubled elements, return empty array
            return []
        
        # Use one instance of the current number and its double
        original.append(num)
        frequency[num] -= 1
        frequency[double] -= 1
    
    return original

# Example usage:
print(find_original_array([1,3,4,2,6,8]))  # Expected output: [1,3,4]
← Back to All Questions