2007. Find Original Array From Doubled Array

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

 

Constraints:

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

Similar Questions:

• Array of Doubled Pairs (Medium)

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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};