Return the index of the node that can be reached from bothnode1andnode2, such that the maximum between the distance fromnode1to that node, and fromnode2to that node is minimized. If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1.
Input: edges =[2,2,3,-1], node1 =0, node2 =1Output: 2Explanation: The distance from node 0 to node 2is1, and the distance from node 1 to node 2is1.The maximum of those two distances is1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.
Example 2:
graph LR
0 --> 1
1 --> 2
1
2
3
4
Input: edges =[1,2,-1], node1 =0, node2 =2Output: 2Explanation: The distance from node 0 to node 2is2, and the distance from node 2 to itself is0.The maximum of those two distances is2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.
Method 1 - Using BFS or single source shortest path#
This problem involves finding a node that can be reached from both node1 and node2 with distances that balance minimisation and maximisation properties. To achieve this efficiently, we perform a breadth-first search (BFS) or single-source shortest path traversal starting from both nodes, capturing the distances to all reachable nodes.
classSolution {
publicintclosestMeetingNode(int[] edges, int node1, int node2) {
int n = edges.length;
int[] dist1 =newint[n];
int[] dist2 =newint[n];
// Fill all distances with a sufficiently large value java.util.Arrays.fill(dist1, Integer.MAX_VALUE);
java.util.Arrays.fill(dist2, Integer.MAX_VALUE);
// BFS helper to calculate distances calculateDistances(edges, node1, dist1);
calculateDistances(edges, node2, dist2);
int ans =-1;
int minDistance = Integer.MAX_VALUE;
// Find the minimum distance node reachable by bothfor (int i = 0; i < n; i++) {
if (dist1[i]!= Integer.MAX_VALUE&& dist2[i]!= Integer.MAX_VALUE) {
int maxDist = Math.max(dist1[i], dist2[i]);
if (maxDist < minDistance || (maxDist == minDistance && i < ans)) {
ans = i;
minDistance = maxDist;
}
}
}
return ans;
}
privatevoidcalculateDistances(int[] edges, int start, int[] dist) {
int n = edges.length;
boolean[] visited =newboolean[n];
int d = 0;
while (start !=-1 &&!visited[start]) {
dist[start]= d++;
visited[start]=true;
start = edges[start];
}
}
}
classSolution:
defclosestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
n = len(edges)
dist1 = [float('inf')] * n
dist2 = [float('inf')] * n
defcalculate_distances(start: int, dist: List[int]) ->None:
visited = [False] * n
d =0while start !=-1andnot visited[start]:
dist[start] = d
visited[start] =True d +=1 start = edges[start]
# Calculate distances calculate_distances(node1, dist1)
calculate_distances(node2, dist2)
ans =-1 min_distance = float('inf')
# Find the minimum distance node reachable by bothfor i in range(n):
if dist1[i] != float('inf') and dist2[i] != float('inf'):
max_dist = max(dist1[i], dist2[i])
if max_dist < min_distance or (max_dist == min_distance and i < ans):
ans = i
min_distance = max_dist
return ans