Skip to main content
Talentd

Find Original Array From Doubled Array - Solution & Explanation

MediumArrayHash TableGreedySorting13 min readAsked at: Amazon, Goldman Sachs, Meta +3
Practice this problem

Problem Statement

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 <= 105
  • 0 <= changed[i] <= 105

Approach Overview

Problem 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 1: Hash Map and Sorting Approach

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Two Pointers Technique

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.

Code

JavaScriptJava

JavaScript

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Sorting

We notice that if the array changed is a double array, then the smallest element in the array changed must also be an element in the original array. Therefore, we can first sort the array changed, and then start from the first element to traverse the array changed in ascending order.

We use a hash table or array cnt to count the occurrence of each element in the array changed. For each element x in the array changed, we first check whether x exists in cnt. If it does not exist, we skip this element. Otherwise, we subtract one from cnt[x], and check whether x times 2 exists in cnt. If it does not exist, we return an empty array directly. Otherwise, we subtract one from cnt[x times 2], and add x to the answer array.

After the traversal, we return the answer array.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array changed.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Map and Sorting Approach

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.

Two Pointers Technique

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.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map and SortingO(n log n)O(n)General case; easiest to implement and reason about during interviews
Two Pointers TechniqueO(n log n)O(n)When you prefer pointer-based traversal after sorting instead of frequency maps

Video Solution

Find Original Array From Doubled Array | Google | Easy Explanation | codestorywithMIK • codestorywithMIK • 13,028 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Original Array From Doubled Array easy or hard?
The problem is rated Medium because the core idea is simple but edge cases can break naive implementations. Handling duplicates, zeros, and ensuring doubles exist for every element requires careful frequency tracking. Understanding why sorting is required is the main conceptual hurdle.
Find Original Array From Doubled Array Python/Java solution
In Python, the solution typically uses collections.Counter after sorting the array and greedily pairing each number with its double. In Java, developers often use HashMap or arrays for frequency counting combined with Arrays.sort. Both implementations follow the same greedy pairing logic and run in O(n log n) time.
How to solve Find Original Array From Doubled Array in O(n)?
Pure O(n) time is difficult because the numbers must typically be processed in sorted order to safely match smaller values with their doubles. Most accepted solutions sort the array first and then use a greedy pairing strategy with a hash map. This results in O(n log n) time overall and linear extra space.
What is the best approach for Find Original Array From Doubled Array?
The most reliable approach sorts the array and uses a hash map to track frequencies. Process numbers from smallest to largest and match each value x with its double 2x. This greedy strategy ensures smaller numbers are paired first and prevents consuming doubles prematurely. The overall complexity is O(n log n) time due to sorting and O(n) space for the frequency map.
Is Find Original Array From Doubled Array asked at Google/Amazon/Meta?
This problem pattern appears in interviews at large tech companies including Amazon, Google, and Meta because it tests greedy reasoning, frequency counting, and array manipulation. Candidates are expected to combine sorting with a hash map or pointer-based pairing to achieve efficient reconstruction.
What data structure is used in Find Original Array From Doubled Array?
A hash table (frequency map) is the primary data structure used in the optimal solution. It stores counts of each value so the algorithm can quickly check whether a corresponding double exists. Sorting is also required so elements are processed in increasing order.
What is the time complexity of Find Original Array From Doubled Array?
The optimal solution runs in O(n log n) time because the array must be sorted before pairing elements. After sorting, each number is processed once with constant-time hash map operations. Space complexity is O(n) for storing element frequencies or tracking used elements.

Ready to solve this problem?

Practice Find Original Array From Doubled Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array of Doubled Pairs

Next

Recover the Original Array