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 <= 10^50 <= changed[i] <= 10^5
The description was taken from https://leetcode.com/problems/find-original-array-from-doubled-array/.
#O(N(Log(N))) Time, O(N) Space
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
if len(changed) < 2 or len(changed) % 2 != 0:
return []
count, output = {}, []
for num in changed:
if num not in count:
count[num] = 1
else:
count[num] += 1
for num in sorted(changed):
if not count[num]:
continue
if num * 2 not in count or not count[num * 2]:
return []
count[num] -= 1
count[num * 2] -= 1
output.append(num)
return outputIn this problem, a number can either be multiplied by two to equal its pair partner, or it can be divided by two to equal its pair partner.
If we had a number that could be paired with a division partner, but it could also be paired with a multiplication partner, how would we choose which number to pair it with?
That is where we may consider a greedy approach, an approach where we sort our input and take care of the cheapest tasks to conserve the most resources. In this case, our resources are numbers to pair.
If we are implementing an algorithm that requires knowing where other numbers are within input or if they exist, that is usually a given that a HashMap should be utilized.
What we can do is place each number and their frequency into a HashMap and then sort the array by absolute values, since we can have negative numbers.
From there, all we need to do is pick a multiplication partner and won't have to worry about a division partner.
We will traverse the array and for each number, we will see if its partner exists by multiplying it by two and referencing the hashmap. After we pair the numbers we will just decrement their frequencies in the HashMap to simulate the pairing then append the lesser partner to the output. If we find a number that we can't pair with its multiplication partner, we will return an empty array.
Note: This problem is nearly the same as Array of Doubled Pairs but with a different output type.
First off, if the length of the input array is less than two or doesn't have an even length, then there is no way that it could be a doubled array so we will return an empty array.
if len(changed) < 2 or len(changed) % 2 != 0:
return []
Otherwise, let's initialize a dictionary to track the count of each number and an output array.
count, output = {}, []
For each number within the changed array, let's initialize its place in our dictionary or increment it if it was already there.
for num in changed:
if num not in count:
count[num] = 1
else:
count[num] += 1
Then, we will traverse the input array, sorted in ascending order.
for num in sorted(changed):
If the current number has been decremented to zero within the input array, then we have already paired this number so we will continue.
if not count[num]:
continue
If the current number multiplied by two is not in the HashMap, then we can't pair this number so we will return an empty array.
We will also return an empty array if the number is there, but has already been paired with a different number and can't be paired with the current one.
if num * 2 not in count or not count[num * 2]:
return []
Otherwise, we will pair these two numbers and append the current number to the output.
count[num] -= 1
count[num * 2] -= 1
output.append(num)
If we have traversed the array and never returned an empty array, that means we were able to pair each number so we will return the output.
return output