Leetcode journey - Question 2007 - Find Original Array From Doubled Array

Problem:

Q2007. Find Original Array From Doubled Array

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

Solution:

Our first approach will be to check if the size of the array is odd, then return an empty array as the array cannot be divided into pairs. We can use multiset to store the elements of the array. (Multiset is a set that can have multiple elements with the same value and it is sorted in ascending order). We can iterate over the multiset and for each element, we can check if the element*2 is present in the multiset or not. If it is present then we can erase the element*2 from the multiset and push the element in the answer vector else we return an empty vector. (as the array cannot be divided into pairs). If we can iterate over the multiset and erase all the elements then we can return the answer vector else we can return an empty vector.

Pseudo Code:

function findOriginalArray(vector changed)
    if size of changed is odd
        return empty vector
    create a multiset s
    for each element i in changed
        insert i in s
    create a vector ans
    while s is not empty
        create a variable x and assign it to the first element of s
        erase the first element of s
        if s.find(x2) is not equal to s.end() (i.e. x2 is present in s)
            erase s.find(x*2)
            push x in ans
        else
            return empty vector
    return ans

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<int> findOriginalArray(vector<int> &changed)
    {
        if (changed.size() % 2 != 0)
            return {};
        multiset<int> s;
        for (int i : changed)
            s.insert(i);
        vector<int> ans;
        while (!s.empty())
        {
            int x = *s.begin();
            s.erase(s.begin());
            if (s.find(x * 2) == s.end()) // if 2*x not found
                return {};
            s.erase(s.find(x * 2));
            ans.push_back(x);
        }
        return ans;
    }
};

int main()
{
    Solution s;
    vector<int> v = {1, 3, 4, 2, 6, 8};
    vector<int> ans = s.findOriginalArray(v);
    for (int i : ans)
        cout << i << " ";
    return 0;
}

Complexity Analysis:

Time Complexity: O(nlogn) (as we are using multiset)
Space Complexity: O(n)
Hope this helps!

• If you have any questions, please leave a comment below. 💭
  

• If you like this article, please share it with your friends. 💖
  

• If you want to read more articles like this, please follow me.
  

Thank you for reading!