LeetCode

## Editorial: LeetCode 2007 Find Original Array From Doubled Array

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).