334. Find Original Array From Doubled Array
Medium
Frequency Reconstruction
Hashing
Problem
An original array was transformed by appending twice every element and then shuffling the result. Given the resulting non-negative integer array changed, reconstruct and return one valid original array. If no original array exists, return an empty array. The returned original values may appear in any order.
Examples
Example 1
Input: [1,3,4,2,6,8]
Output: [1,3,4]
Example 2
Input: [6,3,0,1]
Output: []
Example 3
Input: [1]
Output: []
Constraints
� 1 <= changed.length <= 100000
� 0 <= changed[i] <= 100000
Hints
?? An odd-length changed array can never be valid.
?? Process values from smallest to largest.
?? Match every occurrence of x with an available occurrence of 2 * x.
?? Zero requires an even frequency because zero doubles to zero.
Expected Complexity
Time: O(n log n)
Space: O(n)
Follow-up
Why is processing values in increasing order important?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,3,4,2,6,8]Expected
[1,3,4]