Odd Even Jump LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} arr
3
 * @return {number}
4
 */
5
var oddEvenJumps = function (arr) {
6
  let result = 0;
7
  const len = arr.length;
8
  const map = {}; // { value: index }
9
  const memo = new Array(2).fill(null).map((i) => new Array(len).fill(false));
10

11
  // Build a BST to maintain logN search/Insert
12
  function treeNode(value) {
13
    this.val = value;
14
    this.left = null;
15
    this.right = null;
16
  }
17

18
  const root = new TreeNode(arr[len - 1]);
19

20
  function InsertToBST(val) {
21
    function dfs(node) {
22
      if (node.val < val) {
23
        if (!node.right) node.right = new TreeNode(val);
24
        else dfs(node.right);
25
      }
26
      if (node.val > val) {
27
        if (!node.left) node.left = new TreeNode(val);
28
        else dfs(node.left);
29
      }
30
    }
31

32
    dfs(root);
33
  }
34

35
  memo[0][len - 1] = memo[1][len - 1] = true;
36
  map[arr[len - 1]] = len - 1;
37

38
  //memo[0] odd jumps
39
  //memo[1] even jumps
40

41
  function getNextBig(base) {
42
    // odd jump
43
    if (map[base] !== undefined) {
44
      return base;
45
    }
46
    let result = Infinity;
47
    function dfs(node) {
48
      if (!node) return;
49

50
      if (node.val > base && node.val < result) {
51
        result = node.val;
52
        dfs(node.left);
53
      }
54

55
      if (node.val < base) {
56
        dfs(node.right);
57
      }
58
    }
59

60
    dfs(root);
61

62
    return result === Infinity ? false : result;
63
  }
64

65
  function getNextSmall(base) {
66
    //even jump
67
    if (map[base] !== undefined) {
68
      return base;
69
    }
70
    let result = -Infinity;
71
    function dfs(node) {
72
      if (!node) return;
73

74
      if (node.val < base && node.val > result) {
75
        result = node.val;
76
        dfs(node.right);
77
      }
78

79
      if (node.val > base) {
80
        dfs(node.left);
81
      }
82
    }
83

84
    dfs(root);
85

86
    return result === -Infinity ? false : result;
87
  }
88

89
  for (let i = len - 2; i >= 0; i--) {
90
    let nextBig = getNextBig(arr[i]);
91
    let nextSmall = getNextSmall(arr[i]);
92

93
    memo[0][i] = nextBig ? memo[1][map[nextBig]] : nextBig;
94
    memo[1][i] = nextSmall ? memo[0][map[nextSmall]] : nextSmall;
95
    map[arr[i]] = i;
96
    InsertToBST(arr[i]);
97
  }
98

99
  return memo[0].filter((boo) => boo).length;
100
};