Editorial: LeetCode 2007 Find Original Array From Doubled Array
https://leetcode.com/problems/find-original-array-from-doubled-array/ from Google
Solutions:
1. Brute force (TLE)
Split changed into two array. Check if it’s valid. If it is, return directly and stop searching.
1class Solution {
2public:
3 int N;
4 bool valid(vector<int>& ans, vector<int>& right) {
5 vector<int> x = ans, y = right;
6 sort(begin(x), end(x));
7 sort(begin(y), end(y));
8 for (int i=0; i<N/2; i++) if (x[i]*2 != y[i]) return false;
9 return true;
10 }
11 bool dfs(vector<int>& changed, vector<int>& ans, vector<int>& right, int cur) {
12 if (cur == N) {
13 if (valid(ans, right)) return true;
14 return false;
15 }
16 if (ans.size() < N/2) {
17 ans.push_back(changed[cur]);
18 if (dfs(changed, ans, right, cur+1)) return true;
19 ans.pop_back();
20 }
21 if (right.size() < N/2) {
22 right.push_back(changed[cur]);
23 if (dfs(changed, ans, right, cur+1)) return true;
24 right.pop_back();
25 }
26 return false;
27 }
28 vector<int> findOriginalArray(vector<int>& changed) {
29 N = changed.size();
30 vector<int> ans, right;
31 if (N%2 != 0) return ans;
32 if (dfs(changed, ans, right, 0))
33 return ans;
34 return vector<int>();
35 }
36};
Time complexity: O(2^N). Space O(N)
2. Start from the smallest
We know that if changed contains original, then the smallest element must be in original as all elements are >= 0. We can put the smallest element into ans and delete the double one. Once we finish the smallest one and delete it, the remaining smallest one must be in the ans again …
1class Solution {
2public:
3 vector<int> findOriginalArray(vector<int>& changed) {
4 int N = changed.size();
5 vector<int> ans;
6 if (N%2 != 0) return ans;
7 unordered_map<int, int> cnt;
8 for (auto n : changed) {
9 cnt[n]++;
10 }
11 sort(changed.begin(), changed.end());
12 for (auto n : changed) {
13 if (cnt[n] == 0) continue;
14 ans.push_back(n);
15 cnt[n]--;
16 if (cnt[2*n] == 0) return vector<int>();
17 cnt[2*n]--;
18 }
19 return ans;
20 }
21};
Time complexity: O(NlogN). Space complexity: O(N).
3. Start from the smallest and only sort keys
Small optimization. If the number of different elements is much smaller than N, we can just sort those elements instead of sorting the whole array.
1class Solution {
2public:
3 vector<int> findOriginalArray(vector<int>& changed) {
4 int N = changed.size();
5 vector<int> ans;
6 if (N%2 != 0) return ans;
7 unordered_map<int, int> cnt;
8 for (auto n : changed) cnt[n]++;
9 priority_queue<int, vector<int>, greater<int>> pq;
10 for (auto [k, v] : cnt) pq.push(k);
11 while (pq.size()) {
12 int s = pq.top(); pq.pop();
13 while (cnt[s] > 0) {
14 ans.push_back(s);
15 cnt[s]--;
16 if (cnt[s*2] <= 0) return vector<int>();
17 cnt[s*2]--;
18 }
19 }
20 return ans;
21 }
22};
Time complexity: O(N + KlogK), where K is the number of keys. Space complexity: O(N).