# 2007. Find Original Array From Doubled Array

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`

## Solution

The idea is to use a map to keep the times of each element, and for each value inside the map, we should be able to find out whether it is possible to find a matched pair on the map.

To use a TreeMap, it can help us to guarantee the order of key is always in ascedning order.

Then, for each element,  we can check if we can find another double one inside the map (which will be the current element's paired element), and we also update the paired element's count on the map. &#x20;

Util all the values(count) of the element on the map are 0. We finally solve the problem.

```java
public int[] findOriginalArray(int[] A){
    int n = A.length;
    if(n%2 != 0) return new int[0];
    int[] ret = new int[n/2];
    TreeMap<Integer, Integer> map = new TreeMap<>();
    for(int num : A){
        map.put(num, map.getOrDefault(num, 0)+1);
    }
    int index = 0;
    for(int e : map.keySet()) {
        if(map.get(e) > map.getOrDefault(e*2, 0)){
            return new int[0];
        }
        for(int i = 0; i < map.get(e); i++) {
            ret[index++] = e;
            map.put(e*2, map.get(e*2)-1);        
        }
    }
    return ret;
}
```
