Maximum Employees to Be Invited to a Meeting LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} favorite
3
 * @return {number}
4
 */
5
var maximumInvitations = function (favorite) {
6
  let res = 0;
7
  let len = favorite.length;
8
  // count the number indegree
9
  let indegree = new Array(len).fill(0);
10
  // save the number relation
11
  let rMap = new Map();
12
  for (let i = 0; i < favorite.length; i++) {
13
    indegree[favorite[i]]++;
14

15
    if (rMap.has(favorite[i])) {
16
      let arr = rMap.get(favorite[i]);
17
      arr.push(i);
18
      rMap.set(favorite[i], arr);
19
    } else {
20
      rMap.set(favorite[i], [i]);
21
    }
22
  }
23
  // find the 0 indegree number
24
  let arr = [];
25
  for (let i = 0; i < len; i++) {
26
    if (indegree[i] === 0) {
27
      arr.push(i);
28
    }
29
  }
30
  // check if the circle exist
31
  let search = 0;
32
  // the length of uncircle
33
  let l = 1;
34
  // save the number and the length of uncircle
35
  let lMap = new Map();
36
  while (arr.length > 0) {
37
    let tmp = [];
38
    for (let i = 0; i < arr.length; i++) {
39
      lMap.set(arr[i], l);
40
      let next = favorite[arr[i]];
41
      indegree[next]--;
42
      search++;
43
      if (indegree[next] === 0) {
44
        tmp.push(next);
45
      }
46
    }
47
    // update the length of uncircle
48
    l++;
49
    arr = [...tmp];
50
  }
51

52
  if (search === len) {
53
    // circle not exist
54
  } else {
55
    // circle exist
56
    // find the not 0 indegree number
57
    let keys = find(indegree);
58
    // mark the search number in circle
59
    let circleMap = new Map();
60
    // the length of circle
61
    let circleLen = 1;
62
    // the max length of circle
63
    let maxCircleLen = 0;
64
    // sum the length of circle
65
    let sumCircleLen = 0;
66
    let cArr = [keys[0]];
67

68
    while (cArr.length > 0) {
69
      let tmp = [];
70
      for (let i = 0; i < cArr.length; i++) {
71
        // not find the circle
72
        if (!circleMap.has(cArr[i])) {
73
          circleMap.set(cArr[i], circleLen);
74
          tmp.push(favorite[cArr[i]]);
75
          // find the circle
76
        } else {
77
          maxCircleLen = Math.max(maxCircleLen, circleLen - 1);
78
          // if the length equals 2 then sum the length
79
          if (circleLen - 1 === 2) {
80
            let m =
81
              calc(cArr[i], rMap, lMap) +
82
              calc(favorite[cArr[i]], rMap, lMap) +
83
              2;
84
            sumCircleLen += m;
85
          }
86
          // reset the length
87
          circleLen = 0;
88
          // find the next number not search
89
          for (let i = 0; i < keys.length; i++) {
90
            if (!circleMap.has(keys[i])) {
91
              tmp.push(keys[i]);
92
              break;
93
            }
94
          }
95
        }
96
      }
97
      circleLen++;
98
      cArr = [...tmp];
99
    }
100
    res = Math.max(res, maxCircleLen, sumCircleLen);
101
  }
102

103
  return res;
104
};
105

106
function calc(num, rMap, lMap) {
107
  let res = 0;
108
  let arr = rMap.has(num) ? rMap.get(num) : [];
109
  if (arr.length > 0) {
110
    for (let i = 0; i < arr.length; i++) {
111
      let l = lMap.has(arr[i]) ? lMap.get(arr[i]) : 0;
112
      res = Math.max(res, l);
113
    }
114
  }
115
  return res;
116
}
117

118
function find(arr) {
119
  let res = [];
120
  for (let i = 0; i < arr.length; i++) {
121
    if (arr[i] > 0) {
122
      res.push(i);
123
    }
124
  }
125
  return res;
126
}