Find Original Array From Doubled Array — Problem & Solution
Find Original Array From Doubled Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Original Array From Doubled Array is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An array changed is a doubled array if it was built from some array original by appending twice the value of every element and then shuffling the result.
Given changed, return original sorted in ascending order. If changed is not a doubled array, return an empty array.
Example 1
Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: The doubles 2, 6 and 8 pair off with 1, 3 and 4.
Example 2
Input: changed = [6,3,0,1]
Output: []
Explanation: No valid original array produces this multiset.
Example 3
Input: changed = [1]
Output: []
Explanation: An odd length can never be a doubled array.
Constraints
1 <= changed.length <= 1000000 <= changed[i] <= 100000
Hints for Find Original Array From Doubled Array
Hint 1
An odd length is an immediate rejection.
Hint 2
Process values in increasing order: the smallest remaining value can only ever be an original, never a double.
Hint 3
Zero is the awkward case — it is its own double, so it consumes two zeros per original.
How to solve Find Original Array From Doubled Array
Sort ascending and match greedily. The smallest unmatched value cannot be anyone's double (that would require a smaller positive value still in play), so it must belong to original and be paired with its double.
Approach
- Reject an odd-length input outright.
- Sort a copy and build a frequency map.
- Walk the sorted values. Skip any already consumed (frequency 0).
- Otherwise decrement the value and its double; if the double is unavailable, the input is invalid. Record the value in the answer.
- Return the collected values — they come out ascending because the walk is ascending.
Why it works
In a valid doubled array, the minimum element must be an original: its half would be a smaller element, contradicting minimality (for positive values). Consuming it and its double leaves a strictly smaller valid instance, so induction carries the greedy through.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
0doubles to itself, so a run of zeros must be even and each original consumes two of them.- Iterating over the map's keys in hash order instead of sorted order breaks the greedy argument.
- Decrementing the double before checking it exists can produce negative counts that silently pass later tests.
Reference solution
Python
from typing import List
def findOriginalArray(changed: List[int]) -> List[int]:
if len(changed) % 2 != 0:
return []
s = sorted(changed)
count = {}
for x in s:
count[x] = count.get(x, 0) + 1
out = []
for x in s:
if count.get(x, 0) == 0:
continue
if x == 0:
if count[x] < 2:
return []
count[x] -= 2
out.append(0)
continue
if count.get(x * 2, 0) == 0:
return []
count[x] -= 1
count[x * 2] -= 1
out.append(x)
return outJava
public static int[] findOriginalArray(int[] changed) {
if (changed.length % 2 != 0) return new int[0];
int[] s = changed.clone();
Arrays.sort(s);
HashMap<Integer, Integer> count = new HashMap<>();
for (int x : s) count.put(x, count.getOrDefault(x, 0) + 1);
int[] tmp = new int[s.length / 2];
int m = 0;
for (int x : s) {
if (count.getOrDefault(x, 0) == 0) continue;
if (x == 0) {
if (count.get(0) < 2) return new int[0];
count.put(0, count.get(0) - 2);
tmp[m++] = 0;
continue;
}
if (count.getOrDefault(x * 2, 0) == 0) return new int[0];
count.put(x, count.get(x) - 1);
count.put(x * 2, count.get(x * 2) - 1);
tmp[m++] = x;
}
int[] out = new int[m];
for (int i = 0; i < m; i++) out[i] = tmp[i];
return out;
}C++
vector<int> findOriginalArray(vector<int>& changed) {
if (changed.size() % 2 != 0) return {};
vector<int> s = changed;
sort(s.begin(), s.end());
unordered_map<int, int> count;
for (int x : s) count[x]++;
vector<int> out;
for (int x : s) {
if (count[x] == 0) continue;
if (x == 0) {
if (count[0] < 2) return {};
count[0] -= 2;
out.push_back(0);
continue;
}
if (count[x * 2] == 0) return {};
count[x]--;
count[x * 2]--;
out.push_back(x);
}
return out;
}JavaScript
var findOriginalArray = function(changed) {
if (changed.length % 2 !== 0) return [];
const s = changed.slice().sort(function(a, b) { return a - b; });
const count = {};
for (let i = 0; i < s.length; i++) {
const k = String(s[i]);
count[k] = (count[k] || 0) + 1;
}
const out = [];
for (let i = 0; i < s.length; i++) {
const x = s[i];
const kx = String(x);
if ((count[kx] || 0) === 0) continue;
if (x === 0) {
if (count[kx] < 2) return [];
count[kx] -= 2;
out.push(0);
continue;
}
const k2 = String(x * 2);
if ((count[k2] || 0) === 0) return [];
count[kx]--;
count[k2]--;
out.push(x);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets