Leetcode 2117 Solution

This article provides solution to leetcode question 2117 (find-original-array-from-doubled-array)
Categories:
Tags:
Access this page by simply typing in "lcs 2117" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-original-array-from-doubled-array

Solution

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        vector<int> ans;



        if (changed.size() % 2 == 1)
            return ans;



        map<int, int> m;
        for (auto it = changed.begin(); it != changed.end(); it++)
            m[*it]++;



        while (!m.empty())
        {
            auto it = m.begin();
            int target = 2 * it->first;



            ans.push_back(it->first);
            it->second -= 1;
            if (it->second == 0)
                m.erase(it);



            if (m.find(target) == m.end())
                return vector<int>();



            m[target] -= 1;
            if (m[target] == 0)
                m.erase(target);
        }



        return ans;
    }
};