Jobs

Interviews

Discussions

Find Original Array From Doubled Array

Medium

Verily

2 views

Topics:

ArraysGreedy AlgorithmsHash Table

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

1 <= changed.length <= 10⁵
0 <= changed[i] <= 10⁵

Find Original Array From Doubled Array

Medium

Verily

2 views

Topics:

ArraysGreedy AlgorithmsHash Table

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

1 <= changed.length <= 10⁵
0 <= changed[i] <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within the `changed` array? Can they be negative, zero, or only positive?
If the `changed` array cannot be formed by doubling and shuffling an original array, should I return an empty array or is there a specific error code or exception I should raise?
Can the `changed` array contain duplicate numbers, and if so, how should I handle them when determining the original array?
Is the input array `changed` guaranteed to be of even length if it is a valid doubled array?
If multiple 'original' arrays could potentially produce the `changed` array through doubling and shuffling, is there a specific one I should return, or can I return any valid 'original' array?

Brute Force Solution

Approach

The brute force strategy for finding the original array involves checking every possible combination of numbers to see if one of those combinations, when doubled, produces the given doubled array. It's like trying every possible puzzle piece to see if it fits. We systematically check all possibilities.

Here's how the algorithm would work step-by-step:

First, we take the given list of numbers and consider each number as a potential element of the original array.
For each of these potential elements, we check if its double exists in the given list.
If we find the double, we tentatively add the original number to our potential original array.
We then remove both the original number and its double from the given list and continue checking remaining numbers.
If at any point we cannot find the double of a number in the list, we discard the current attempt and try a different starting number.
We repeat this process, exploring all possible starting numbers and combinations until we either find an original array that, when doubled, matches the input, or we have exhausted all possibilities.
If we find such an array, that's our answer. If not, it means no such original array exists.

Code Implementation

def find_original_array_brute_force(doubled_array):
    array_length = len(doubled_array)

    if array_length % 2 != 0:
        return []

    for i in range(array_length):
        potential_original = []
        remaining_numbers = doubled_array[:]

        potential_original.append(remaining_numbers[i])
        del remaining_numbers[i]

        temp_remaining_numbers = remaining_numbers[:]
        temp_potential_original = potential_original[:]

        while len(temp_potential_original) <= array_length // 2:
            found_match = False
            for j in range(len(temp_remaining_numbers)):
                if temp_remaining_numbers[j] == 2 * temp_potential_original[-1]:
                    del temp_remaining_numbers[j]
                    found_match = True

                    # Only append if a match is found
                    if len(temp_remaining_numbers) > 0:
                        temp_potential_original.append(temp_remaining_numbers[0])
                        del temp_remaining_numbers[0]
                    
                    break
            if not found_match:
                break
        
        if len(temp_potential_original) == array_length // 2 and found_match:
            
            return potential_original

    return []

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2) – The described brute force approach iterates through each of the n elements of the input array. For each element, it searches for its double within the remaining elements. In the worst-case scenario, finding the double requires iterating through the remaining portion of the array, which, on average, is proportional to n. Therefore, since we perform a potentially n-sized search for each of the n elements, the total number of operations approximates to n * n. Thus, the time complexity is O(n^2).

Space Complexity

O(N) – The brute force solution, as described, uses a modified version of the input list. In the worst-case scenario, we create a tentative original array which could potentially hold up to N/2 elements (where N is the length of the doubled array). Additionally, we are repeatedly removing elements from the given list, which in some implementations might involve creating a new list without those elements in each iteration. Therefore, the auxiliary space used is proportional to the size of the input array, resulting in O(N) space complexity.

Optimal Solution

Approach

The key to solving this problem efficiently is to work backwards from the largest numbers. We use a counting method to keep track of how many times each number appears, and then intelligently pair each number with its double to reconstruct the original array.

Here's how the algorithm would work step-by-step:

First, count how many times each number shows up in the doubled array.
Then, process the numbers from largest to smallest.
For each number, check if its double is present and available.
If the double exists, we know that the original array must contain the current number. Therefore, reduce counts of both the current number and its double.
If we ever run into a number whose double isn't available, we know it's impossible to reconstruct the original array.
At the end, if we've successfully paired off all the numbers, we can assemble the original array from the numbers we identified along the way.

Code Implementation

def find_original_array(doubled_array):
    number_counts = {}
    for number in doubled_array:
        number_counts[number] = number_counts.get(number, 0) + 1

    doubled_array.sort()
    original_array = []

    for number in reversed(doubled_array):
        if number_counts[number] == 0:
            continue

        double_value = number / 2

        #If number is odd, then it can't be double of anything.
        if number % 2 != 0:
            return []

        # This makes sure that the number can be formed from a doubling.
        if double_value not in number_counts or number_counts[double_value] == 0:
            return []

        original_array.append(int(double_value))

        # Reduce the counts of the original number and its double.
        number_counts[number] -= 1
        number_counts[double_value] -= 1

    return original_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The solution first counts the frequency of each number in the input array of size n, which takes O(n) time. Then, it sorts the unique numbers based on their absolute values in descending order, which takes O(n log n) time. For each number, it checks the availability of its double. In the worst case, we might iterate through all numbers, performing constant-time operations (decrementing counts) for each, which contributes O(n). Therefore, the dominant factor is the sorting step, leading to an overall time complexity of O(n log n).

Space Complexity

O(N) – The primary auxiliary space is used by the counting method to track the frequency of each number in the doubled array. This counting mechanism, likely implemented using a hash map or an array, stores counts for each distinct number. In the worst case, where all N numbers in the input array are distinct, the hash map or array will store N counts. Thus, the auxiliary space scales linearly with the input size N.

Edge Cases

Case	How to Handle
Null input array	Return an empty array immediately to avoid NullPointerException.
Empty input array	Return an empty array immediately as no original array can be formed.
Input array with an odd number of elements	Return an empty array immediately because a doubled array must have an even number of elements.
Input array contains zero values	Handle zero values carefully since 2*0 is 0 and requires special counting/handling to avoid incorrect pairings.
Input array contains negative numbers	Sort the input array, then iterate and verify the existence of doubled negative values correctly.
Large numbers in the array that could cause integer overflow when doubled	Consider using a larger data type (e.g., long) or implement overflow checking if the doubled value is used in calculations.
Input array contains duplicate values where some are doubled and some are not	The algorithm should correctly identify pairs even with duplicates by using a frequency map.
No valid original array exists	The algorithm should return an empty array when after processing the entire input, not all numbers could be paired appropriately.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within the `changed` array? Can they be negative, zero, or only positive?
If the `changed` array cannot be formed by doubling and shuffling an original array, should I return an empty array or is there a specific error code or exception I should raise?
Can the `changed` array contain duplicate numbers, and if so, how should I handle them when determining the original array?
Is the input array `changed` guaranteed to be of even length if it is a valid doubled array?
If multiple 'original' arrays could potentially produce the `changed` array through doubling and shuffling, is there a specific one I should return, or can I return any valid 'original' array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we take the given list of numbers and consider each number as a potential element of the original array.
For each of these potential elements, we check if its double exists in the given list.
If we find the double, we tentatively add the original number to our potential original array.
We then remove both the original number and its double from the given list and continue checking remaining numbers.
If at any point we cannot find the double of a number in the list, we discard the current attempt and try a different starting number.
We repeat this process, exploring all possible starting numbers and combinations until we either find an original array that, when doubled, matches the input, or we have exhausted all possibilities.
If we find such an array, that's our answer. If not, it means no such original array exists.

Code Implementation

def find_original_array_brute_force(doubled_array):
    array_length = len(doubled_array)

    if array_length % 2 != 0:
        return []

    for i in range(array_length):
        potential_original = []
        remaining_numbers = doubled_array[:]

        potential_original.append(remaining_numbers[i])
        del remaining_numbers[i]

        temp_remaining_numbers = remaining_numbers[:]
        temp_potential_original = potential_original[:]

        while len(temp_potential_original) <= array_length // 2:
            found_match = False
            for j in range(len(temp_remaining_numbers)):
                if temp_remaining_numbers[j] == 2 * temp_potential_original[-1]:
                    del temp_remaining_numbers[j]
                    found_match = True

                    # Only append if a match is found
                    if len(temp_remaining_numbers) > 0:
                        temp_potential_original.append(temp_remaining_numbers[0])
                        del temp_remaining_numbers[0]
                    
                    break
            if not found_match:
                break
        
        if len(temp_potential_original) == array_length // 2 and found_match:
            
            return potential_original

    return []

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number shows up in the doubled array.
Then, process the numbers from largest to smallest.
For each number, check if its double is present and available.
If the double exists, we know that the original array must contain the current number. Therefore, reduce counts of both the current number and its double.
If we ever run into a number whose double isn't available, we know it's impossible to reconstruct the original array.
At the end, if we've successfully paired off all the numbers, we can assemble the original array from the numbers we identified along the way.

Code Implementation

def find_original_array(doubled_array):
    number_counts = {}
    for number in doubled_array:
        number_counts[number] = number_counts.get(number, 0) + 1

    doubled_array.sort()
    original_array = []

    for number in reversed(doubled_array):
        if number_counts[number] == 0:
            continue

        double_value = number / 2

        #If number is odd, then it can't be double of anything.
        if number % 2 != 0:
            return []

        # This makes sure that the number can be formed from a doubling.
        if double_value not in number_counts or number_counts[double_value] == 0:
            return []

        original_array.append(int(double_value))

        # Reduce the counts of the original number and its double.
        number_counts[number] -= 1
        number_counts[double_value] -= 1

    return original_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Return an empty array immediately to avoid NullPointerException.
Empty input array	Return an empty array immediately as no original array can be formed.
Input array with an odd number of elements	Return an empty array immediately because a doubled array must have an even number of elements.
Input array contains zero values	Handle zero values carefully since 2*0 is 0 and requires special counting/handling to avoid incorrect pairings.
Input array contains negative numbers	Sort the input array, then iterate and verify the existence of doubled negative values correctly.
Large numbers in the array that could cause integer overflow when doubled	Consider using a larger data type (e.g., long) or implement overflow checking if the doubled value is used in calculations.
Input array contains duplicate values where some are doubled and some are not	The algorithm should correctly identify pairs even with duplicates by using a frequency map.
No valid original array exists	The algorithm should return an empty array when after processing the entire input, not all numbers could be paired appropriately.