2007 - Find Original Array From Doubled Array

Difficulty: Medium | Pattern: Greedy + Sorted Counter | Company tags: Amazon, Google

Problem Statement

An original array original was doubled to create a changed array by appending the double of every element in original, then shuffling the resulting array.

Given an array changed, return original if changed is a doubled array, or return an empty array if changed is not a doubled array.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]  (doubled array would be [1,2,3,6,4,8] shuffled)

Example 2:

Input: changed = [6,3,0,1]
Output: []

Example 3:

Input: changed = [3,1]
Output: []  (odd length → can't be doubled)

Algorithm Flow

Approach: Sort + Counter Matching — O(n log n)

Key insight: Sort the array. Process smallest elements first. For each element x, its double 2x must also be in the array. Use a Counter to track remaining elements.

from collections import Counter

def findOriginalArray(changed: list[int]) -> list[int]:
    if len(changed) % 2 != 0:
        return []
    
    count = Counter(changed)
    result = []
    
    for x in sorted(count.keys()):
        if count[x] == 0:
            continue
        
        # Special case: 0 must appear even number of times
        if x == 0:
            if count[0] % 2 != 0:
                return []
            result.extend([0] * (count[0] // 2))
            count[0] = 0
            continue
        
        if count[2*x] < count[x]:
            return []
        
        result.extend([x] * count[x])
        count[2*x] -= count[x]
        count[x] = 0
    
    return result

Dry Run

changed = [1,3,4,2,6,8]

count: 1→1, 2→1, 3→1, 4→1, 6→1, 8→1

x	count[2x]	action	result
1	count[2]=1 gte 1	add [1], count[2]-=1	[1]
2	count[2]=0, skip		[1]
3	count[6]=1 gte 1	add [3], count[6]-=1	[1,3]
4	count[8]=1 gte 1	add [4], count[8]-=1	[1,3,4]

Result: [1,3,4] ✓

Complexity

• Time: O(n log n) — sort dominates
• Space: O(n)

Key Terms

Term	Definition
Counter matching	Using a frequency map to pair each value with its required partner (here, 2x) instead of searching the array repeatedly.
Greedy smallest-first	Processing elements in sorted order guarantees the smallest unmatched value can only be an "original" element, never a doubled one.
Multiset / frequency map	A Counter tracking how many unmatched copies of each value remain as pairs are consumed.
Zero-value edge case	0 doubles to itself (2*0 = 0), so it needs special handling: it must appear an even number of times.

FAQ

Q1: Why must we sort before matching? A: Sorting guarantees that when we visit value x, no smaller unmatched value can be its "double." This lets us safely treat x as an original and consume 2x from the counter without ambiguity.

Q2: Can this be solved without sorting, e.g., using a heap? A: Yes — a min-heap gives the same ascending-order guarantee with O(n log n) push/pop operations, which is asymptotically the same as sorting. Sorting is simpler to implement.

Q3: What happens if changed contains duplicate values, like [2,2,4,4]? A: The Counter handles multiplicities naturally: count[2]=2, count[4]=2. Since count[4] >= count[2], both 2's are matched, consuming both 4's, giving original = [2,2].

Q4: Why does 0 need special-case logic? A: Since 2*0 == 0, the generic check count[2x] < count[x] would compare count[0] against itself and never fail, incorrectly accepting an odd count of zeros. We explicitly require count[0] to be even.

Q5: What's the time complexity bottleneck? A: Sorting the unique keys is O(n log n); the matching pass over the counter is O(n). Sorting dominates, so overall complexity is O(n log n).

Quick Revision

• Problem: recover original such that changed = shuffled original + doubled(original).
• If len(changed) is odd, immediately return [].
• Build a frequency Counter of all values in changed.
• Process unique values in ascending sorted order — smallest unmatched value is always an original.
• Special-case x == 0: count of zeros must be even, add half as many zeros to result.
• For x != 0, require count[2x] >= count[x]; otherwise return [].
• On match, add count[x] copies of x to result and subtract that many from count[2x].
• Time: O(n log n) for sorting; Space: O(n) for the counter and result.

Related Problems

• 1-TwoSum — same "use a hash map/counter instead of brute force" trick.
• 15-3Sum — sorting first to enable greedy/two-pointer matching.
• Pattern match: any "pair up elements by a derived relationship" problem (e.g., LeetCode 954 Array of Doubled Pairs, which is this exact problem under a different number).