2007. Find Original Array From Doubled Array

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 maybe 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

Let`s Code IT!

/**
 * @param {number[]} changed
 * @return {number[]}
 */
var findOriginalArray = function(changed) {
    if (changed.length % 2 === 1) {
        return [];
    }

    var frequency = [];
    var index_frequency = 0;
    var maxLength = Math.pow(10, 5) + 1;
    while (index_frequency < maxLength) {
        frequency[index_frequency++] = 0;
    }


    for (let n of changed) {
        frequency[n]++;
    }

    if (frequency[0] % 2 === 1) {
        return [];
    }

    var original = [];
    var index_original = 0;
    for (let i = 0; i < maxLength; i++) {
        while (2 * i < maxLength && frequency[i] > 0 && frequency[2 * i] > 0) {
            original[index_original++] = i;
            frequency[i]--;
            frequency[2 * i]--;
        }
    }
    return (index_original === changed.length / 2) ? original : [];
};

Conclusion
That’s all folks! In this post, we solved LeetCode problem #2007. Find Original Array From Doubled Array
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!