Find Original Array From Doubled Array - Leetcode Solution

Problem:

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 the original array of integers. If the original array can not be recovered, return an empty array.

Example 1:

Input: changed = [1,3,2,4] Output: [2,4,1,3] Explanation: The array [2,4,1,3] is transformed as follows: - append twice the value of 1, which yields [2,1,4,3]. - shuffle the array at random to obtain [2,4,1,3]. The final result is [2,4,1,3].

Example 2:

Input: changed = [6,3,0,1] Output: [] Explanation: The original array cannot be recovered from changed.

Solution:

This is a simple problem with an easy solution. We can recover the original array from a given doubled array by following the below steps:

1. Sort the given array in ascending order.
2. Initialize an empty array "res".
3. Loop through the given array until the length of the array.
4. Divide the current element of the given array by 2. If the division of the current element is not in the given array then return an empty array as it means, it is not possible to recover the original array from the given array.
5. If the division of the current element is in the given array then remove it from the given array and append the quotient to the "res" array.
6. Return the "res" array.

Let's see this in action with the help of code:

class Solution: def findOriginalArray(self, changed: List[int]) -> List[int]: changed.sort() res = [] while changed: x = changed.pop(0) if (2x) not in changed: return [] else: changed.remove(2x) res.append(x) return res

Time Complexity: O(nlogn) Space Complexity: O(n)

1