2007. Find Original Array From Doubled Array

T: O(nlogn + n)

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

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)

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

*/