Binary Trees With Factors LeetCode solution in JavaScript

1
/** https://leetcode.com/problems/binary-trees-with-factors/
2
 * @param {number[]} arr
3
 * @return {number}
4
 */
5
var numFactoredBinaryTrees = function (arr) {
6
  // Memo
7
  this.memo = new Map();
8

9
  // Sort the `arr`
10
  arr.sort((a, b) => a - b);
11

12
  // Create hashmap so we can easily find the index of the value
13
  let map = new Map();
14
  arr.forEach((val, idx) => map.set(val, idx));
15

16
  // We are going to calculate total numbers of binary trees by assigning each `arr[i]` as the root of the tree
17
  let count = 0;
18
  for (let i = arr.length - 1; i >= 0; i--) {
19
    count += dp(arr, map, i);
20
  }
21

22
  // Perform mod on the final result
23
  let mod = 10 ** 9 + 7;
24
  return count % mod;
25
};
26

27
var dp = function (arr, map, currIdx) {
28
  // Return from memo
29
  if (this.memo.has(currIdx) === true) {
30
    return this.memo.get(currIdx);
31
  }
32

33
  // Start the count as 1 to include the current node
34
  let count = 1;
35

36
  // Loop through all number before `arr[currIdx]`
37
  for (let i = currIdx - 1; i >= 0; i--) {
38
    // The `left` and `right` node of the root
39
    // The `right` node is basically the root divided by the `left` since the rule stated that the root is product of its children
40
    let left = arr[i];
41
    let right = arr[currIdx] / left;
42

43
    // Ignore if the root is not a product of its children
44
    if (arr[currIdx] % left !== 0 || map.has(right) === false) {
45
      continue;
46
    }
47

48
    // Get the count for `left` node and `right` node
49
    let leftCount = dp(arr, map, i);
50
    let rightCount = dp(arr, map, map.get(right));
51

52
    // Total count is multiplication of `left` and `right` count because each combination of is unique
53
    count += leftCount * rightCount;
54
  }
55

56
  // Set memo
57
  this.memo.set(currIdx, count);
58

59
  return count;
60
};