Find Original Array From Doubled Array LeetCode solution in Java

1
class Solution {
2
  public int[] findOriginalArray(int[] changed) {
3

4
    Arrays.sort(changed);
5

6
    if (changed.length % 2 != 0) return new int[0];
7

8
    int mid = changed.length / 2;
9

10
    int[] res = new int[mid];
11

12
    int[] freq = new int[100001];
13

14
    for (int no : changed) freq[no]++;
15

16
    int idx = 0;
17

18
    for (int no : changed) {
19
      if (freq[no] > 0 && no * 2 <= 100000 && freq[no * 2] > 0) {
20
        freq[no]--;
21
        freq[no * 2]--;
22
        res[idx++] = no;
23
      }
24
    }
25

26
    for (int i = 0; i < freq.length; i++) {
27
      if (freq[i] != 0) return new int[0];
28
    }
29

30
    return res;
31
  }
32
}