Find Original Array From Doubled Array LeetCode solution in JavaScript

1
// Idea is to sort the input array first then start traversing the array
2
// now if we saw half of the current element before and that half is unmatched then
3
// match both of them otherwise note the occurence of current element inorder
4
// to match it with its double element in the future
5

6
// Time -> O(nlogn) due to sorting
7
// Space -> O(n) due to map
8

9
/**
10
 * @param {number[]} changed
11
 * @return {number[]}
12
 */
13
var findOriginalArray = function (changed) {
14
  const n = changed.length;
15
  if (n % 2 === 1) return [];
16

17
  let original = [];
18
  let map = new Map();
19

20
  changed.sort((a, b) => {
21
    return a - b;
22
  });
23

24
  for (let ele of changed) {
25
    const half = ele / 2;
26
    if (map.has(half) && map.get(half) > 0) {
27
      original.push(half);
28
      map.set(half, map.get(half) - 1);
29
    } else {
30
      map.set(ele, map.has(ele) ? map.get(ele) + 1 : 1);
31
    }
32
  }
33

34
  if (original.length !== n / 2) return [];
35

36
  return original;
37
};