---
tags: leetcode
---

# [2007. Find Original Array From Doubled Array](https://leetcode.com/problems/find-original-array-from-doubled-array/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

class Solution {
public:
    vector<int> findOriginalArray(vector<int> &changed) {
        if (changed.size() & 0x01) {
            return {};
        }

        unordered_map<int, int> numCnt;
        for (int i = 0; i < changed.size(); ++i) {
            ++numCnt[changed[i]];
        }
        sort(changed.begin(), changed.end());

        vector<int> original;
        for (auto &num : changed) {
            auto numIter = numCnt.find(num), num2Iter = numCnt.find(num << 1);
            if (numIter == numCnt.end() || num2Iter == numCnt.end() ||
                numIter->second <= 0 || num2Iter->second <= 0) {
                continue;
            }
            if (num == 0 && numIter->second < 2) {
                continue;
            }

            original.push_back(num);
            --numIter->second;
            --num2Iter->second;
        }

        if ((original.size() << 1) != changed.size()) {
            return {};
        }
        return original;
    }
};

## Time Complexity
$O(nlogn)$
$n$ is the length of `changed`.
## Space Complexity
$O(n)$
# Miscellane
<!--
# Test Cases

[1,3,4,2,6,8]

[6,3,0,1]

[1]

* TLE: https://leetcode.com/submissions/detail/720419213/testcase/
* Wrong Answer:

[0,0,0,0]

* Wrong Answer:

[1,4,2,1]

* Wrong Answer:

[4,4,16,20,8,8,2,10]

-->