Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5

Input:
changed = [6,3,0,1]
Output:
 []
Explanation: changed is not a doubled array.

Example 3:

1
2
3
4
5

Input:
changed = [1]
Output:
 []
Explanation: changed is not a doubled array.

Solution

This problem is similar to Array of Doubled Pairs.

Method 1 – Sorting and Frequency Map

Intuition

The main idea is to pair each number with its double. By sorting the array, we can always try to pair the smallest available number first, which helps handle negative numbers and zeros correctly. We use a frequency map to track how many times each number appears and greedily match each number with its double.

Approach

  1. Sort the array to process numbers in order, handling negatives and zeros properly.
  2. Use a frequency map to count occurrences of each number.
  3. For each number in the sorted array:
    • If its frequency is zero, skip it.
    • If its double’s frequency is zero, return an empty array.
    • Otherwise, decrement the frequency of both the number and its double and add the number to the answer.
  4. If all numbers are paired successfully, return the answer array.

Dry Run

Let’s dry run the algorithm for changed = [1,3,4,2,6,8]:

  • Sort: [1,2,3,4,6,8]
  • Frequency: {1:1, 2:1, 3:1, 4:1, 6:1, 8:1}
  • Process 1: freq[1]=1, freq[2]=1 → add 1, freq[1]=0, freq[2]=0
  • Process 2: freq[2]=0 (skip)
  • Process 3: freq[3]=1, freq[6]=1 → add 3, freq[3]=0, freq[6]=0
  • Process 4: freq[4]=1, freq[8]=1 → add 4, freq[4]=0, freq[8]=0
  • Process 5: freq[6]=0 (skip)
  • Process 6: freq[8]=0 (skip)
  • Result: [1,3,4]

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of changed, due to sorting and linear scan.
  • 🧺 Space complexity: O(n), for the frequency map and answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        int n = changed.size();
        if (n % 2) return {};
        sort(changed.begin(), changed.end());
        unordered_map<int, int> freq;
        for (int num : changed) freq[num]++;
        vector<int> ans;
        for (int num : changed) {
            if (freq[num] == 0) continue;
            if (freq[2 * num] == 0) return {};
            ans.push_back(num);
            freq[num]--;
            freq[2 * num]--;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 != 0) return new int[0];
        Arrays.sort(changed);
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : changed) freq.put(num, freq.getOrDefault(num, 0) + 1);
        int[] ans = new int[n / 2];
        int idx = 0;
        for (int num : changed) {
            if (freq.get(num) == 0) continue;
            if (freq.getOrDefault(2 * num, 0) == 0) return new int[0];
            ans[idx++] = num;
            freq.put(num, freq.get(num) - 1);
            freq.put(2 * num, freq.get(2 * num) - 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def findOriginalArray(self, changed: list[int]) -> list[int]:
        n = len(changed)
        if n % 2 != 0:
            return []
        changed.sort()
        freq = {}
        for num in changed:
            freq[num] = freq.get(num, 0) + 1
        ans = []
        for num in changed:
            if freq[num] == 0:
                continue
            if freq.get(2 * num, 0) == 0:
                return []
            ans.append(num)
            freq[num] -= 1
            freq[2 * num] -= 1
        return ans