Watch 10 video solutions for Find Original Array From Doubled Array, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by codestorywithMIK has 11,582 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |