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.

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

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;
}