# 2007. Find Original Array From Doubled Array

T: O(nlogn + n)

S: O(hash map size + n/2)

```java
class Solution {
    // the key is doing in order
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n%2 != 0) {
            return new int[]{};
        }
        Arrays.sort(changed);
        
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[n/2];
        int idx = 0;
        for (int i = n -1; i >= 0 ;i--) {
            int twice = changed[i]*2;
            
            if (map.containsKey(twice)) {
                int count = map.get(twice);
                if (count == 1) {
                    map.remove(twice);
                } else {
                    map.put(twice, count-1);
                }
                res[idx++] = changed[i];
            } else {
                map.put(changed[i], map.getOrDefault(changed[i], 0)+1);
            }
        }
        return idx == n/2 ? res : new int[]{};
    }
}

/*

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


from end to 0

map.put 8 1
map.put 6 1
map.put 2 1
4*2 = 8 => remove
3
*/
```

## newest explaination

```
T: O(nlogn)
S: O(n)
```

```java
class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        Map<Integer, Integer> map = new HashMap<>();
        if (n % 2 != 0) {
            return new int[]{};
        }
        int[] res = new int[n/2];
        Arrays.sort(changed);
        int idx = 0;
        for (int i = n - 1; i >= 0; i--) {
            int num = changed[i];
            if (!map.containsKey(2*num)) {
                map.put(num, map.getOrDefault(num, 0)+1);
            } else {
                res[idx++] = num;
                map.put(2*num, map.get(2*num)-1);
                if (map.get(2*num) == 0) {
                    map.remove(2*num);
                }
            }
        }
        return idx != (n/2) ? new int[]{} : res;
    }
}

/*
T: O(nlogn)
S: O(n)

from question, so half numbers is generated from another half numbers (by Doubled)

so if we sort, gen numbers must some is in the last, so try to find from end

hashmap put generated numbers, for following check
use hashmap<num, count>, count is for duplicate number, so needs record count (if number is all unique, use set is fine)

how to find ?
doubled the num (2*num), if existed in hashmap<num, count>, means num is the src, remove (2*num) from hashmap
not existed, means num is generated one, put in hashmap<num, count>

edge case:
changed.len % 2 == 0

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]

sort first
         <-
1 2 3 4 6 8

8*2 = 16 => x => put in hashmap, means 8 is gen by some number
6*2 = 12 => x => put in hashmap, means 6 is gen by some number
4*2 = 8 => o, res = [4], dont put 4 in hashmap, remove 8
3*2 = 6 => o, res = [3, 4], dont put 3 in hashmap. remove 6
2*2 = 4 => x, => put 2 in hashmap
1*2 = 2 => o, res [1,3,4], dont put 1 in hashmap. remove 2

Input: changed = [6,3,0,1]
Output: []

0, 1, 3, 6

6*2 = 12 => x, hashmap[6]
3*2 = 6 => o, res[3], hashmap[]
1*2 = 2 => x => hashmap[1]
0*2 = 0 => x => hashmap[1, 0]

res[3].len != n/2

*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/hashtable/2007.-find-original-array-from-doubled-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.