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.
1import java.util.*;
2
This Java solution uses a similar counting method with a sorted array. The main idea is attempting to find every number's double and build the original array by iteration using a HashMap for count and validations.