Count Pairs Of Nodes LeetCode solution in JavaScript

1
var countPairs = function (n, edges, queries) {
2
  const degree = Array(n + 1).fill(0);
3
  const edgesMap = new Map();
4
  const countMemo = new Map();
5
  const answer = [];
6

7
  for (let [u, v] of edges) {
8
    degree[u]++;
9
    degree[v]++;
10
    const key = `${Math.min(u, v)}-${Math.max(u, v)}`;
11
    edgesMap.set(key, (edgesMap.get(key) || 0) + 1);
12
  }
13
  const sortedDegree = [...degree.slice(1)].sort((a, b) => a - b);
14

15
  for (let num of queries) {
16
    let cnt;
17
    if (countMemo.has(num)) cnt = countMemo.get(num);
18
    else {
19
      cnt = calculateCount(num);
20
      countMemo.set(num, cnt);
21
    }
22
    answer.push(cnt);
23
  }
24

25
  function calculateCount(num) {
26
    let low = 0,
27
      high = sortedDegree.length - 1,
28
      cnt = 0;
29

30
    while (low < high) {
31
      const sum = sortedDegree[low] + sortedDegree[high];
32

33
      if (sum > num) {
34
        cnt += high - low;
35
        high--;
36
      } else low++;
37
    }
38

39
    for (let [key, val] of edgesMap) {
40
      const [u, v] = key.split("-").map(Number);
41

42
      if (degree[u] + degree[v] > num) {
43
        const newSum = degree[u] + degree[v] - val;
44
        if (newSum <= num) cnt--;
45
      }
46
    }
47
    return cnt;
48
  }
49
  return answer;
50
};