##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2007.html

# 2007. Find Original Array From Doubled Array (Medium)

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 = 
Output: []
Explanation: changed is not a doubled array.


Constraints:

• 1 <= changed.length <= 105
• 0 <= changed[i] <= 105

Similar Questions:

## Solution 1. Frequency Map

Sort the array A. Keep removing the smallest element n and 2 * n from the array, and put n into the answer until A becomes empty. Anytime we can’t do the removal, we return empty array.

// OJ: https://leetcode.com/problems/find-original-array-from-doubled-array/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> findOriginalArray(vector<int>& A) {
if (A.size() % 2) return {};
multiset<int> s(begin(A), end(A));
vector<int> ans;
for (int i = 0; i < N; i += 2) {
int n = *s.begin();
ans.push_back(n);
s.erase(s.begin());
if (s.find(2 * n) == s.end()) return {}; // Don't use s.count(2 * n) == 0 here since it's an O(N) operation for multiset.
s.erase(s.find(2 * n));
}
return ans;
}
};


We can keep a frequency map in map<int, int> m, and remove elements of the same value in batch.

// OJ: https://leetcode.com/problems/find-original-array-from-doubled-array/
// Time: O(NlogK) where N is the length of A, and K is the number of unique elements in A
// Space: O(N)
class Solution {
public:
vector<int> findOriginalArray(vector<int>& A) {
if (A.size() % 2) return {};
map<int, int> m; // a frequency map
for (int n : A) m[n]++;
vector<int> ans;
while (m.size()) {
auto [n, cnt] = *m.begin();
if (n == 0) {
if (cnt % 2) return {}; // count of 0 is odd.
for (int j = 0; j < cnt / 2; ++j) ans.push_back(0);
m.erase(0);
} else {
if (m[2 * n] < cnt) return {}; // not enough 2n available.
m.erase(n);
for (int j = 0; j < cnt; ++j) ans.push_back(n);
m[2 * n] -= cnt;
if (m[2 * n] == 0) m.erase(2 * n);
}
}
return ans;
}
};


Or

// OJ: https://leetcode.com/problems/find-original-array-from-doubled-array/
// Time: O(N + KlogK) where N is the length of A, and K is the number of unique elements in A
// Space: O(N)
class Solution {
public:
vector<int> findOriginalArray(vector<int>& A) {
if (A.size() % 2) return {};
unordered_map<int, int> m;
for (int n : A) m[n]++;
vector<int> nums;
for (auto [n, cnt] : m) nums.push_back(n);
sort(begin(nums), end(nums));
vector<int> ans;
for (int n : nums) {
if (m[2 * n] < m[n]) return {};
for (int i = 0; i < m[n]; ++i, --m[2 * n]) ans.push_back(n);
}
return ans;
}
};