LeetCode 2007 - Find Original Array From Doubled Array

LeetCode Problem 2007

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an array called changed, which was supposedly created from another array called original.

The transformation process works like this:

1. Take every number in original.
2. Append its doubled value, meaning 2 * x.
3. Shuffle all the numbers together.

For example, if:

original = [1, 3, 4]

then the doubled values are:

[2, 6, 8]

After combining and shuffling:

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

Our task is to reconstruct and return the original array.

If no valid original array exists, we must return an empty array.

A very important observation is that every value in the original array must have a matching doubled value somewhere else in the array. This means:

• If a number x appears k times in the original array,
• Then the number 2 * x must also appear at least k times in changed.

The constraints are large:

• changed.length can be up to 10^5
• Values can also be up to 10^5

These constraints immediately rule out expensive quadratic approaches. We need something close to O(n log n) or better.

Another important detail is that the length of changed must be even. Since every original element contributes exactly two numbers to the final array, a valid doubled array always contains an even number of elements.

There are several tricky edge cases:

• Arrays with odd length are automatically invalid.
• The number 0 is special because doubling zero still gives zero. Zeroes must appear an even number of times.
• Duplicates can complicate matching.
• Greedy matching in the wrong order can fail. For example, if we process large values before small ones, we may consume numbers needed later.

The key challenge is pairing every number with its double without accidentally reusing elements.

Approaches

Brute Force Approach

A straightforward brute force strategy would attempt to repeatedly:

1. Pick a number.
2. Search for its doubled value somewhere else in the array.
3. Remove both numbers if found.
4. Continue until all elements are processed.

Conceptually, this works because every original value must pair with its doubled counterpart.

However, this approach is inefficient because searching and removing elements from arrays repeatedly is expensive.

If we use a list structure and perform linear searches for every element, the complexity becomes approximately O(n^2).

With n up to 100000, this is far too slow.

Optimal Approach

The key insight is that matching must happen in sorted order.

Suppose we process smaller numbers first:

• If we encounter x,
• Then we try to reserve one occurrence of 2 * x.

This works because smaller values should claim their doubles before larger values consume them.

For example:

[1,2,2,4]

If we process 2 before 1, we might incorrectly use a 4 too early and lose the ability to pair properly.

Sorting avoids this issue.

We use a frequency map to track how many copies of each number remain available.

The algorithm becomes:

1. Sort the array.
2. Count frequencies.
3. For each number in sorted order:

• If none remain, skip it.

• If its double does not exist, return [].

• Otherwise:

• Add the number to the original array.

• Decrease counts for both the number and its double.

This greedy strategy is correct because smaller values always secure their required doubles first.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Repeated searching and removal
Optimal	O(n log n)	O(n)	Sorting plus frequency counting

Algorithm Walkthrough

1. First, check whether the length of changed is odd.

A valid doubled array must contain exactly twice as many elements as the original array. Therefore, the total number of elements must be even.

If the length is odd, immediately return an empty array. 2. Sort the array in ascending order.

Sorting is essential because we want to process smaller values before larger ones. This guarantees that when we try to match a number with its double, the smaller number claims the larger one first. 3. Build a frequency map.

We use a hash map where:

frequency[value] = remaining occurrences

This allows constant time lookup and update operations. 4. Iterate through the sorted array.

For each number num:

• If its frequency is already zero, it means this value has already been used in a previous pairing, so skip it.
• Otherwise, attempt to find num * 2.

5. Check whether the doubled value exists.

If:

frequency[num * 2] == 0

then no valid pairing exists, so return an empty array. 6. Form a valid pair.

Since both values exist:

• Add num to the answer.
• Decrease the count of num.
• Decrease the count of num * 2.

7. Continue until all numbers are processed.

If the process completes successfully, return the constructed original array.

Why it works

The correctness relies on processing numbers in sorted order.

Every number must pair with exactly one doubled value. By handling smaller numbers first, we guarantee that larger numbers are not prematurely consumed by incorrect matches.

The frequency map ensures each element is used exactly once.

If at any point a required double is unavailable, the array cannot possibly represent a valid doubled array.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        n = len(changed)

        if n % 2 == 1:
            return []

        changed.sort()

        frequency = Counter(changed)
        original = []

        for num in changed:
            if frequency[num] == 0:
                continue

            doubled = num * 2

            if frequency[doubled] == 0:
                return []

            original.append(num)

            frequency[num] -= 1
            frequency[doubled] -= 1

        return original

The implementation starts by checking whether the array length is odd. If so, the function immediately returns an empty list because a valid doubled array must contain pairs.

Next, the array is sorted. This is one of the most important steps because it guarantees that smaller values are processed before their doubles.

A Counter is then created to track how many copies of each value remain unused.

During iteration:

• If a value has already been consumed, it is skipped.
• Otherwise, the algorithm searches for its doubled value.
• If the doubled value is unavailable, reconstruction is impossible.
• If the doubled value exists, both frequencies are decreased and the current number is added to the answer.

The algorithm finishes once every valid pair has been processed.

Go Solution

package main

import "sort"

func findOriginalArray(changed []int) []int {
	n := len(changed)

	if n%2 == 1 {
		return []int{}
	}

	sort.Ints(changed)

	frequency := make(map[int]int)

	for _, num := range changed {
		frequency[num]++
	}

	original := make([]int, 0, n/2)

	for _, num := range changed {
		if frequency[num] == 0 {
			continue
		}

		doubled := num * 2

		if frequency[doubled] == 0 {
			return []int{}
		}

		original = append(original, num)

		frequency[num]--
		frequency[doubled]--
	}

	return original
}

The Go implementation follows the same logic as the Python version.

A map[int]int is used instead of Python's Counter. Sorting is done using sort.Ints.

One small difference is that Go returns an empty slice:

[]int{}

instead of Python's [].

Integer overflow is not a concern here because values are bounded by 10^5, so doubling remains safely within Go's integer range.

Worked Examples

Example 1

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

After sorting:

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

Initial frequency map:

Value	Count
1	1
2	1
3	1
4	1
6	1
8	1

Processing steps:

Current Number	Double Needed	Action	Original
1	2	pair found	[1]
2	4	skipped because count is 0	[1]
3	6	pair found	[1,3]
4	8	pair found	[1,3,4]
6	12	skipped because count is 0	[1,3,4]
8	16	skipped because count is 0	[1,3,4]

Final answer:

[1,3,4]

Example 2

changed = [6,3,0,1]

After sorting:

[0,1,3,6]

Frequency map:

Value	Count
0	1
1	1
3	1
6	1

Processing begins with 0.

The algorithm needs another 0 because:

0 * 2 = 0

But only one zero exists.

Therefore:

frequency[0] == 1

After consuming one zero, no second zero remains.

The algorithm returns:

[]

Example 3

changed = [1]

The array length is odd.

A valid doubled array must contain pairs.

Therefore the algorithm immediately returns:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Frequency map and output array

The frequency operations themselves are constant time on average because hash map operations are O(1).

Although we iterate through the array once after sorting, the sorting step costs O(n log n), which becomes the dominant term.

The additional space comes from storing frequencies and the reconstructed original array.

Test Cases

from collections import Counter

class Solution:
    def findOriginalArray(self, changed):
        if len(changed) % 2 == 1:
            return []

        changed.sort()
        frequency = Counter(changed)

        original = []

        for num in changed:
            if frequency[num] == 0:
                continue

            doubled = num * 2

            if frequency[doubled] == 0:
                return []

            original.append(num)

            frequency[num] -= 1
            frequency[doubled] -= 1

        return original

solution = Solution()

assert solution.findOriginalArray([1,3,4,2,6,8]) == [1,3,4]  # standard valid example

assert solution.findOriginalArray([6,3,0,1]) == []  # invalid because zero lacks pair

assert solution.findOriginalArray([1]) == []  # odd length cannot be valid

assert solution.findOriginalArray([0,0]) == [0]  # simplest valid zero case

assert solution.findOriginalArray([0,0,0,0]) == [0,0]  # multiple zero pairs

assert solution.findOriginalArray([2,4,4,8]) == [2,4]  # duplicate values

assert solution.findOriginalArray([1,2,2,4]) == [1,2]  # overlapping chains

assert solution.findOriginalArray([2,1,4,8]) == []  # missing doubled pair

assert solution.findOriginalArray([]) == []  # empty input edge case

assert solution.findOriginalArray([4,2,8,1]) == [1,4]  # shuffled valid input

Test Summary

Test	Why
[1,3,4,2,6,8]	Standard valid doubled array
[6,3,0,1]	Invalid because zero cannot pair
[1]	Odd-length invalid case
[0,0]	Smallest valid zero pairing
[0,0,0,0]	Multiple zero duplicates
[2,4,4,8]	Duplicate handling
[1,2,2,4]	Chain-style pairing
[2,1,4,8]	Missing required pair
[]	Empty array behavior
[4,2,8,1]	Valid shuffled arrangement

Edge Cases

Odd Length Arrays

If the array length is odd, reconstruction is impossible because every original element contributes exactly two elements to the doubled array.

A naive implementation might still attempt matching and waste computation time. This solution immediately rejects odd-length arrays in constant time.

Zero Values

Zero is a special case because:

0 * 2 = 0

This means zero must pair with another zero.

An odd number of zeroes is invalid. The frequency-based approach naturally handles this because each pairing consumes two zeroes.

Duplicate Numbers

Duplicate values can easily break incorrect greedy approaches.

Consider:

[2,4,4,8]

The correct original array is:

[2,4]

The frequency map correctly tracks how many copies remain available, ensuring each occurrence is matched exactly once.

Overlapping Pair Relationships

Some numbers can act both as original values and doubled values.

For example:

[1,2,2,4]

Here:

• 1 pairs with 2
• another 2 pairs with 4

Processing in sorted order is critical. If larger numbers were processed first, valid smaller-number pairings could be destroyed accidentally.