Create Find Original Array From Doubled Array.java

varunu28 · web-flow · commit 962882e422b0 · 2021-09-18T14:33:45.000-07:00
diff --git a/Medium/Find Original Array From Doubled Array.java b/Medium/Find Original Array From Doubled Array.java
@@ -0,0 +1,21 @@
+class Solution {
+  public int[] findOriginalArray(int[] changed) {
+    if (changed.length % 2 != 0) {
+      return new int[]{};
+    }
+    int[] answer = new int[changed.length / 2];
+    int idx = 0;
+    Map<Integer, Long> map = Arrays.stream(changed).boxed()
+        .collect(Collectors.groupingBy(Function.identity(), TreeMap::new, Collectors.counting()));
+    for (Integer key : map.keySet()) {
+      if (map.get(key) > map.getOrDefault(key * 2, 0L)) {
+        return new int[0];
+      }
+      for (int i = 0; i < map.get(key); i++) {
+        answer[idx++] = key;
+        map.put(key * 2, map.get(key * 2) - 1);
+      }
+    }
+    return answer;
+  }
+}
