Find Original Array From Doubled Array
Medium · Arrays & Hashing · Array · Hash Table · Greedy · Sorting
Problem
An integer array original is turned into a doubled array changed by appending twice the value of every element of original and then shuffling the result.
Given changed, return original if changed is a doubled array, in any order. Otherwise, return an empty array.
When changed is a doubled array, the values of original are fully determined, so the answer is checked as a multiset: any order is accepted.
Examples
Input: changed = [6,2,3,12,4,6] Output: [2,3,6]
2 pairs with 4, 3 with 6, and the other 6 with 12.
Input: changed = [5,1,2] Output: []
An odd-length array cannot be split into pairs.
Input: changed = [0,0,0,0,7,14] Output: [0,0,7]
The double of 0 is 0, so four zeros make two (0, 0) pairs; 7 pairs with 14.
Constraints
- 1 <= len(changed) <= 10^5
- 0 <= changed[i] <= 10^5
Approaches
- Baseline: sort, then scan for each double — time O(n²), space O(n)
Follow-up
With negative numbers allowed, the smallest value is no longer safe: the double of -3 is -6, which is smaller. Process values in increasing absolute value instead; a value with the smallest magnitude cannot be the double of anything else. Since values here are at most 10^5, a count array with a pass from 0 upward also replaces the sort and makes the solution O(n + V).
Related problems
Start free on Cariara · Coding problems · System design studio
