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.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5std::vector<int> findOriginalArray(std::vector<int>& changed) {
6 if (changed.size() % 2 != 0) return {};
7 std::sort(changed.begin(), changed.end());
8 std::unordered_map<int, int> count;
9 for (int num : changed) {
10 count[num]++;
11 }
12 std::vector<int> original;
13 for (int num : changed) {
14 if (count[num] == 0) continue;
15 if (count[num * 2] == 0) return {};
16 original.push_back(num);
17 count[num]--;
18 count[num * 2]--;
19 }
20 return original;
21}This C++ solution is similar to the Python one, using a hash map to count occurrences. It sorts the numbers, attempts to find pairs, and checks if both elements of the pair exist in the hash map. If finding a pair is impossible, it returns an empty vector.
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.