Find Original Array From Doubled Array

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

Problem Statement

An integer array original is transformed into a doubled array changed by appending twice the value of every element in the original, and then randomly shuffling the resulting array.

Given an array changed, return the original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in the 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 <= 10⁵
• 0 <= changed[i] <= 10⁵

Disclaimer: The above problem might look a bit tricky but it is a rather simple one. Before proceeding forward towards the solution it is recommended to try first!!

Intuition

If we closely look at the problem we will notice that there is a very easy way to check if the given array of integers forms a doubled array. If the given array is a doubled array we will be able to remove all the elements from the given array ( i and 2*i). Thus, making the array empty. Therefore, only if the array is empty after removing all the elements it will be a doubled array.

But we also need to return the original array. This can be achievable by preserving the ith element of the array while deleting the pair i and 2*i.

Also, a point to note here is that the array will only be a doubled array if it contains an even number of elements.

Brainstorm🤔: Can you figure out a way to preserve the ith element while removing the ith and 2*ith element?

Approach

• First, we will create an empty array ‘ans’ to hold the original array after removing the doubles.
• Next, we will sort the given array. This will help us to delete the smallest elements and it’s doubled first from the array. After removing the smallest element and its double, there will be another element that will be the smallest.
• In order to check if we can delete all the elements of the given array, we will create a map that will contain the frequency of elements present in the array.
• Next, we will traverse the array and keep on adding the ith element into the ‘ans’ array and decreasing the count of ith and 2*ith element. If at a point we found that the 2*ith element has the map value as 0 or it is not present in the map then the given array is not a doubled array.
• If we are able to completely traverse the array, then it will be a doubled array and we will return ‘ans’ array holding the original array.

Code

C++

Python

Complexity

• T(n): O(n)
• S(n): O(n)

If you like the post, don’t forget to share it with your peers and give your reactions!