Sponsored
Sponsored
This approach utilizes a hash map to count occurrences of elements and sorting to efficiently find element pairs. First, the input array is sorted, and then iteratively each element is processed to find its double using the hash map. If a valid pair is found, both are adjusted accordingly in the map to avoid reuse. If at the end the map ends up having unprocessed values, it indicates that the array cannot form a doubled array, thus returning an empty array.
Time Complexity: O(n log n) due to sorting and O(n) for iterating, total O(n log n).
Space Complexity: O(n) for the hash map.
1def findOriginalArray(changed):
2 if len(changed) % 2 != 0:
3 return [] # Cannot form pairs if length is odd
4 from collections import Counter
5 changed.sort()
6 count = Counter(changed)
7 original = []
8 for x in changed:
9 if count[x] == 0:
10 continue
11 if count[2 * x] == 0:
12 return []
13 original.append(x)
14 count[x] -= 1
15 count[2 * x] -= 1
16 return originalThis Python solution sorts the changed array and uses a hash map (via Counter) to count frequencies. It finds pairs by iterating sorted numbers and adjusts counts making sure each number and its double are in the count. If a match isn't found during iteration, it returns an empty list.
This approach uses a two-point strategy over a sorted array to match each number with its double. Start two pointers: the first at the beginning and the second just after it. Iterate through the array attempting to pair the number at the first pointer with its double at the second pointer. Valid pairs are those which multiply perfectly and do not leave remainder elements. Return an empty array if any mismatch occurs.
Time Complexity: O(n log n) due to sorting and O(n) for the pairing process, total O(n log n).
Space Complexity: O(n) due to the counting object.
1function findOriginalArray(changed) {
2This JavaScript solution relies on counting occurrences using an object and tries to find each element's double in a sorted array. If a match cannot be found, an empty array is returned. Otherwise, it builds the original array as it iterates.