Find Closest Node to Given Two Nodes LeetCode solution in C++

1
class Solution {
2
 public:
3
  int closestMeetingNode(vector<int> &edges, int node1, int node2) {
4
    // special case, if node1 and node2 are same the answer will be itself
5
    if (node1 == node2) return node1;
6

7
    int n = edges.size();
8
    // distance vectors for node1 and node2
9
    vector<int> m1(n, -1);
10
    vector<int> m2(n, -1);
11
    int ans = -1;
12
    int maxD = n + 1;
13

14
    int node = node1;
15
    int dist = 0;
16
    // calculate distance from node1
17
    while (node != -1 && m1[node] == -1) {
18
      m1[node] = dist;
19
      dist++;
20
      node = edges[node];
21
    }
22

23
    node = node2;
24
    dist = 0;
25
    // calculate distance from node2 while checking for the same node in
26
    // distance vector for node1
27
    while (node != -1 && m2[node] == -1) {
28
      if (m1[node] != -1) {
29
        if (maxD > max(dist, m1[node])) {
30
          ans = node;
31
          maxD = max(dist, m1[node]);
32
        } else if (maxD == max(dist, m1[node])) {
33
          if (ans > node) ans = node;
34
        }
35
      }
36

37
      m2[node] = dist;
38
      dist++;
39
      node = edges[node];
40
    }
41

42
    return ans;
43
  }
44
};