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 <= 1050 <= changed[i] <= 105Problem Overview: You receive an array that was formed by taking an original array, doubling every value, and shuffling the result. Your task is to reconstruct the original array. If no valid original array exists, return an empty array.
Approach 1: Hash Map and Sorting (O(n log n) time, O(n) space)
This is the most common and reliable approach. First sort the array so smaller numbers are processed before their doubles. Maintain a frequency map using a hash table. For each number x, check whether a matching 2 * x exists in the map. If it does, decrement the count of the double and add x to the result. If the double does not exist, reconstruction is impossible. Sorting ensures you never consume a value before its smaller counterpart has been processed, which prevents pairing conflicts. This approach combines sorting with hash table lookups for efficient pairing.
The key insight is greedy pairing from smallest to largest. When numbers are processed in sorted order, the smallest value must belong to the original array because its half cannot appear later in the list. Each lookup and update in the hash map takes constant time, so the dominant cost is sorting.
Approach 2: Two Pointers Technique (O(n log n) time, O(n) space)
This approach also starts by sorting the array. Use two pointers to simulate matching between original values and their doubles. The first pointer scans candidate original numbers, while the second pointer searches ahead for 2 * x. A visited structure or count tracking prevents reusing numbers already paired. Whenever a valid double is found, record the original value and advance both pointers accordingly.
The technique works because sorting clusters related values together. Pointer movement effectively performs the greedy pairing while avoiding repeated scans of earlier elements. Although it still requires sorting, pointer traversal itself is linear. This method is easier to reason about if you prefer pointer-based iteration over direct frequency maps. It relies on the same greedy idea often used in array pairing problems.
Recommended for interviews: The hash map + sorting solution is what most interviewers expect. It clearly demonstrates control over greedy reasoning, frequency counting, and efficient pairing logic. Showing a brute-force pairing idea first proves you understand the constraints, but implementing the sorted hash map strategy signals strong problem-solving instincts and clean complexity analysis.
This approach utilizes a hash map to count occurrences of elements and sorting to efficiently find element pairs. First, the input array is sorted, and then iteratively each element is processed to find its double using the hash map. If a valid pair is found, both are adjusted accordingly in the map to avoid reuse. If at the end the map ends up having unprocessed values, it indicates that the array cannot form a doubled array, thus returning an empty array.
This Python solution sorts the changed array and uses a hash map (via Counter) to count frequencies. It finds pairs by iterating sorted numbers and adjusts counts making sure each number and its double are in the count. If a match isn't found during iteration, it returns an empty list.
Time Complexity: O(n log n) due to sorting and O(n) for iterating, total O(n log n).
Space Complexity: O(n) for the hash map.
This approach uses a two-point strategy over a sorted array to match each number with its double. Start two pointers: the first at the beginning and the second just after it. Iterate through the array attempting to pair the number at the first pointer with its double at the second pointer. Valid pairs are those which multiply perfectly and do not leave remainder elements. Return an empty array if any mismatch occurs.
This JavaScript solution relies on counting occurrences using an object and tries to find each element's double in a sorted array. If a match cannot be found, an empty array is returned. Otherwise, it builds the original array as it iterates.
JavaScript
Java
Time Complexity: O(n log n) due to sorting and O(n) for the pairing process, total O(n log n).
Space Complexity: O(n) due to the counting object.
| Approach | Complexity |
|---|---|
| Hash Map and Sorting Approach | Time Complexity: O(n log n) due to sorting and O(n) for iterating, total O(n log n). |
| Two Pointers Technique | Time Complexity: O(n log n) due to sorting and O(n) for the pairing process, total O(n log n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map and Sorting | O(n log n) | O(n) | General case; easiest to implement and reason about during interviews |
| Two Pointers Technique | O(n log n) | O(n) | When you prefer pointer-based traversal after sorting instead of frequency maps |
Find Original Array From Doubled Array | Google | Easy Explanation | codestorywithMIK • codestorywithMIK • 11,582 views views
Watch 9 more video solutions →Practice Find Original Array From Doubled Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor