Find Original Array From Doubled Array

Problem Description

Given an integer 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.

Key Insights

• Each element in the original array corresponds to exactly two elements in the changed array: the original element and its double.
• The frequency of each element in the changed array must be even, as each number must appear once as itself and once as its double.
• The order of elements does not matter, so we can sort the array to simplify finding and removing pairs.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(n) - for storing the frequency of elements.

Solution

The solution involves using a hash map (or a frequency dictionary) to count occurrences of each number in the changed array. We then sort the array and iterate through it, attempting to construct the original array by checking for each number if its double exists in the frequency map. If it does, we reduce its count and add the original number to the result. If we can't find a necessary double for any element, we can conclude that changed is not a valid doubled array.

Code Solutions