Skip to content

2359. Find Closest Node to Given Two Nodes 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int closestMeetingNode(vector<int>& edges, int node1, int node2) {
    constexpr int kMax = 10000;
    const vector<int> dist1 = getDist(edges, node1);
    const vector<int> dist2 = getDist(edges, node2);
    int minDist = kMax;
    int ans = -1;

    for (int i = 0; i < edges.size(); ++i)
      if (min(dist1[i], dist2[i]) >= 0) {
        const int maxDist = max(dist1[i], dist2[i]);
        if (maxDist < minDist) {
          minDist = maxDist;
          ans = i;
        }
      }

    return ans;
  }

 private:
  vector<int> getDist(const vector<int>& edges, int u) {
    vector<int> dist(edges.size(), -1);
    int d = 0;
    while (u != -1 && dist[u] == -1) {
      dist[u] = d++;
      u = edges[u];
    }
    return dist;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int closestMeetingNode(int[] edges, int node1, int node2) {
    final int kMax = 10000;
    final int[] dist1 = getDist(edges, node1);
    final int[] dist2 = getDist(edges, node2);
    int minDist = kMax;
    int ans = -1;

    for (int i = 0; i < edges.length; ++i)
      if (Math.min(dist1[i], dist2[i]) >= 0) {
        final int maxDist = Math.max(dist1[i], dist2[i]);
        if (maxDist < minDist) {
          minDist = maxDist;
          ans = i;
        }
      }

    return ans;
  }

  private int[] getDist(int[] edges, int u) {
    int[] dist = new int[edges.length];
    Arrays.fill(dist, -1);
    int d = 0;
    while (u != -1 && dist[u] == -1) {
      dist[u] = d++;
      u = edges[u];
    }
    return dist;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
    kMax = 10000
    dist1 = self._getDist(edges, node1)
    dist2 = self._getDist(edges, node2)
    minDist = kMax
    ans = -1

    for i, (d1, d2) in enumerate(zip(dist1, dist2)):
      if min(d1, d2) >= 0:
        maxDist = max(d1, d2)
        if maxDist < minDist:
          minDist = maxDist
          ans = i

    return ans

  def _getDist(self, edges: List[int], u: int) -> List[int]:
    dist = [-1] * len(edges)
    d = 0
    while u != -1 and dist[u] == -1:
      dist[u] = d
      d += 1
      u = edges[u]
    return dist