# Find Original Array From Doubled Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-original-array-from-doubled-array)
Canonical: https://scaleengineer.com/dsa/problems/find-original-array-from-doubled-array
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Verily](https://scaleengineer.com/companies/verily)
---
## 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_.

**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`

# Approaches
## Brute Force with Sorting
This approach is a straightforward, brute-force method. The main idea is to sort the input array first. Sorting helps because for any positive number `x`, it ensures that `x` will always appear before its double `2*x` in the array. After sorting, we iterate through the array. For each number, we treat it as an element of the `original` array and then linearly scan the rest of the array to find its corresponding double. We use a boolean array to keep track of which elements have been used to avoid pairing them more than once.
**Time:** O(N^2), where N is the length of the `changed` array. The sorting takes O(N log N), but the nested loops for finding pairs dominate, resulting in a quadratic time complexity. · **Space:** O(N), where N is the length of the `changed` array. This is for the `used` array and the `original` list which can grow up to size N/2.
**Pros:** Relatively simple to conceptualize and implement.
**Cons:** The time complexity of O(N^2) is highly inefficient and will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
The algorithm begins by handling the base case: an array with an odd number of elements cannot be a doubled array, so we return an empty array immediately. Then, we sort the `changed` array. This is a key step that simplifies pairing. We iterate through the sorted array with an index `i`. If the element `changed[i]` has not been used, we add it to our potential `original` array. We then start a nested loop with index `j` from `i+1` to find `changed[i] * 2`. To prevent using the same element twice, we maintain a `used` boolean array. If we find an unused match `changed[j] == changed[i] * 2`, we mark both elements as used and move to the next element in the outer loop. If we iterate through the entire array for a given `changed[i]` and cannot find its double, we conclude that the array is not a valid doubled array and return an empty array.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 != 0) {
            return new int[0];
        }
        Arrays.sort(changed);
        List<Integer> originalList = new ArrayList<>();
        boolean[] used = new boolean[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            int num = changed[i];
            int target = num * 2;
            boolean found = false;
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && changed[j] == target) {
                    used[j] = true;
                    found = true;
                    break;
                }
            }
            if (found) {
                originalList.add(num);
                count++;
            } else {
                return new int[0];
            }
        }

        if (count != n / 2) {
            return new int[0];
        }

        return originalList.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
- Check if the length of the `changed` array is odd. If it is, it cannot be a doubled array, so return an empty array.
- Sort the `changed` array in non-decreasing order.
- Create a boolean array `used` of the same size as `changed`, initialized to `false`, to keep track of numbers that have been paired.
- Initialize an empty list `original` to store the result.
- Iterate through the sorted `changed` array from left to right.
- For each element `num` at index `i`:
  - If `used[i]` is `true`, it means this number has already been used as a double for a smaller number, so skip it.
  - Mark `used[i]` as `true` and add `num` to the `original` list.
  - Perform a linear search for `num * 2` in the rest of the array (from index `i + 1`).
  - If an unused `num * 2` is found at index `j`, mark `used[j]` as `true` and stop the search for this `num`.
  - If an unused `num * 2` is not found, it means `changed` is not a valid doubled array. Return an empty array.
- If the loop completes successfully, the `original` list contains the result. Convert it to an array and return it.

## Sorting with a Hash Map
This approach significantly improves the time complexity by replacing the linear search for a double with a constant-time hash map lookup. We first count the frequencies of all numbers. Then, we sort the array to ensure we always process a number `x` before its potential double `2x`. As we iterate through the sorted array, we use the frequency map to find and consume pairs `(x, 2x)`. If we can successfully pair up all the numbers, we have found the original array.
**Time:** O(N log N), where N is the length of `changed`. The sorting step is the most time-consuming part. Building the map and iterating through the sorted array both take O(N) time. · **Space:** O(N), where N is the length of `changed`. The space is used for the frequency map and the result array.
**Pros:** Much more efficient than the brute-force approach, with O(N log N) complexity.; The logic is robust and handles various edge cases like zeros and duplicates correctly.; Works for any range of integer values.
**Cons:** The O(N log N) time complexity from sorting is the bottleneck.; Requires O(N) extra space for the hash map, which can be significant.
### Explanation
The first step is to check for the odd length edge case. We then build a frequency map of all numbers in `changed`. A `HashMap` is suitable for this. After counting, we sort the `changed` array. The sort is essential to avoid greedy mistakes, for instance, in an array like `[2, 4, 8]`, we must pair `(2, 4)` first, not `(4, 8)`. By processing the sorted array `[2, 4, 8]`, we first encounter `2`. We look for its double, `4`, in the frequency map. We find it, use both, and add `2` to our result. Then we move to `4`, but its count in the map is now zero (as it was used as a double), so we skip it. Finally, we process `8`, but cannot find its double `16`, so we correctly identify that this is not a valid doubled array. This process of decrementing counts in the map effectively 'removes' numbers as they are paired.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 != 0) {
            return new int[0];
        }

        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : changed) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        Arrays.sort(changed);

        int[] original = new int[n / 2];
        int index = 0;

        for (int num : changed) {
            if (freq.get(num) == 0) {
                continue;
            }

            freq.put(num, freq.get(num) - 1);
            int target = num * 2;

            if (freq.getOrDefault(target, 0) > 0) {
                freq.put(target, freq.get(target) - 1);
                original[index++] = num;
            } else {
                return new int[0];
            }
        }

        return original;
    }
}
```
### Algorithm
- Check if the length of `changed` is odd. If so, return an empty array.
- Create a hash map to store the frequency of each number in the `changed` array.
- Sort the `changed` array. This is crucial to ensure that for any `x > 0`, we process `x` before `2*x`.
- Initialize an empty list or an array `original` of size `N/2` to store the result.
- Iterate through each `num` in the sorted `changed` array:
  - If the frequency of `num` in the map is 0, it means it has already been used as a double, so we skip it.
  - Decrement the frequency of `num` in the map.
  - Calculate the double: `target = num * 2`.
  - Check if the `target` exists in the map and has a frequency greater than 0.
  - If yes, decrement the frequency of `target` and add `num` to the `original` array.
  - If no, a pair cannot be formed. Return an empty array.
- If the loop completes, it means all numbers were successfully paired. Return the `original` array.

## Frequency Array (Counting Sort)
This is the most efficient approach, which is possible due to the problem's constraints on the range of values in the `changed` array. Instead of a general-purpose sort and hash map, we can use a frequency array (a specialized form of counting sort). We create an array to hold the counts of each number from 0 up to the maximum possible value. By iterating through this frequency array from smallest to largest, we can pair numbers with their doubles in linear time, avoiding the O(N log N) overhead of a comparison sort.
**Time:** O(N + K), where N is the length of `changed` and K is the maximum possible value (`10^5`). O(N) to build the frequency array and O(K) to iterate through it to find pairs. This is linear time. · **Space:** O(N + K), where N is the input size and K is the maximum possible value of an element (`10^5`). Space is required for the frequency array (`O(K)`) and the result array (`O(N)`).
**Pros:** Optimal time complexity of O(N + K), which is linear.; Avoids the overhead of comparison sorting and hash map operations.
**Cons:** The space complexity is dependent on the maximum possible value in the input (K), not just the input size N. If K is very large, this approach becomes infeasible.; It is only applicable when the range of input values is known and reasonably small.
### Explanation
This method capitalizes on the constraint that `0 <= changed[i] <= 10^5`. We can declare an integer array `counts` of size `2 * 10^5 + 1` to store the frequency of each number. We make a single pass through `changed` to populate this `counts` array. Then, we iterate through the `counts` array itself, from `i = 0` to `10^5`. This ordered iteration ensures we always process a number `i` before its double `2*i`. For each `i`, if `counts[i]` is positive, we must find `counts[i]` corresponding doubles at index `2*i`. We check if `counts[2*i]` has at least `counts[i]` elements. If not, the pairing is impossible, and we return an empty array. If it does, we add `i` to our result `counts[i]` times and decrement `counts[2*i]` by `counts[i]`. The case for `i=0` is handled separately first: an odd count of zeros is invalid, otherwise, we pair them up. This approach achieves linear time complexity because we only make a few passes over the input array and the fixed-size `counts` array.

```java
class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 != 0) {
            return new int[0];
        }

        int[] counts = new int[200001];
        for (int num : changed) {
            counts[num]++;
        }

        int[] original = new int[n / 2];
        int k = 0;

        // Handle zeros
        if (counts[0] % 2 != 0) {
            return new int[0];
        }
        for (int i = 0; i < counts[0] / 2; i++) {
            original[k++] = 0;
        }

        for (int i = 1; i <= 100000; i++) {
            if (counts[i] > 0) {
                int target = i * 2;
                // Check if we have enough doubles
                if (counts[target] < counts[i]) {
                    return new int[0];
                }
                // Use the doubles
                counts[target] -= counts[i];
                // Add the original numbers to the result
                for (int j = 0; j < counts[i]; j++) {
                    original[k++] = i;
                }
            }
        }

        // If k is not n/2, it means there were leftover numbers that were not doubles of anything
        return k == n / 2 ? original : new int[0];
    }
}
```
### Algorithm
- Check if the length of `changed` is odd. If so, return an empty array.
- Given the constraint `0 <= changed[i] <= 10^5`, create a frequency array `counts` of size `2 * 10^5 + 1`.
- Populate the `counts` array by iterating through `changed` and incrementing `counts[num]` for each number.
- Initialize an `original` array of size `N/2` and a result index `k = 0`.
- Handle the special case of zero: if `counts[0]` is odd, return `[]`. Otherwise, add `counts[0] / 2` zeros to the `original` array.
- Iterate from `i = 1` up to `10^5`.
  - If `counts[i]` is greater than 0, it means we have `counts[i]` instances of the number `i` that must be from the `original` array (since we are iterating in increasing order).
  - We need to find `counts[i]` instances of its double, `2*i`.
  - Check if `counts[2*i]` is less than `counts[i]`. If it is, we don't have enough doubles, so return `[]`.
  - If we have enough doubles, subtract `counts[i]` from `counts[2*i]` to mark them as used.
  - Add the number `i` to the `original` array `counts[i]` times.
- After the loop, if the number of elements added to `original` (`k`) is equal to `N/2`, return `original`. Otherwise, return `[]` (this handles leftover numbers that couldn't be paired).

# Solutions
### Java

```java
class Solution {
public
  int[] findOriginalArray(int[] changed) {
    int n = changed.length;
    if (n % 2 == 1) {
      return new int[]{};
    }
    Arrays.sort(changed);
    int[] cnt = new int[changed[n - 1] + 1];
    for (int x : changed) {
      ++cnt[x];
    }
    int[] ans = new int[n / 2];
    int i = 0;
    for (int x : changed) {
      if (cnt[x] == 0) {
        continue;
      }
      if (x * 2 >= cnt.length || cnt[x * 2] <= 0) {
        return new int[]{};
      }
      ans[i++] = x;
      cnt[x]--;
      cnt[x * 2]--;
    }
    return i == n / 2 ? ans : new int[]{};
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findOriginalArray(vector<int> &changed) {
    int n = changed.size();
    if (n & 1) {
      return {};
    }
    sort(changed.begin(), changed.end());
    vector<int> cnt(changed.back() + 1);
    for (int &x : changed) {
      ++cnt[x];
    }
    vector<int> ans;
    for (int &x : changed) {
      if (cnt[x] == 0) {
        continue;
      }
      if (x * 2 >= cnt.size() || cnt[x * 2] <= 0) {
        return {};
      }
      ans.push_back(x);
      --cnt[x];
      --cnt[x * 2];
    }
    return ans.size() == n / 2 ? ans : vector<int>();
  }
};

```

### Python

```python
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]: n = len(changed) if n & 1: return [] cnt = Counter(changed) changed . sort() ans = [] for x in changed: if cnt[x] == 0: continue if cnt[x * 2] <= 0: return [] ans . append(x) cnt[x] -= 1 cnt[x * 2] -= 1 return ans if len(ans) == n // 2 else []

```