Find the Original Array From a Doubled Array
Google● MediumNEW GRADPHONE SCREENProblem statement
An unknown array original contains non-negative integers. A changed array was formed by appending twice every value in original, then shuffling all values.
Given changed, reconstruct original and return it in nondecreasing order. Return an empty array when no valid original array exists.
Each occurrence is a separate element. In particular, every original zero requires a second zero as its doubled partner.
Function
findOriginalArray(changed: int[]) → int[]Examples
Example 1
changed = [1,3,4,2,6,8]return = [1,3,4]Values 1, 3, and 4 pair with 2, 6, and 8.
Example 2
changed = [6,3,0,1]return = []No ordering can pair every value with its double.
Example 3
changed = [0,0,2,4]return = [0,2]One zero pairs with the other zero, and 2 pairs with 4.
Constraints
0 <= changed.length <= 200000.changed.lengthis even.0 <= changed[i] <= 1000000000.