Sponsored
Sponsored
We can perform a Breadth-First Search (BFS) from both node1 and node2 to compute shortest distances to all other nodes. Since BFS is useful for finding shortest paths in unweighted graphs, it suits our needs in this problem.
By storing distances from both starting nodes in separate arrays and iterating through all nodes, we can find the node minimizing the maximum of both distances.
Time Complexity: O(n) since each node is processed in the queue at most once.
Space Complexity: O(n) for storing distances.
1from collections import deque
2
3class Solution:
4 def bfs(self, edges, start):
5 n = len(edges)
6 dist = [-1] * n
7 queue = deque([start])
8 dist[start] = 0
9 while queue:
10 node = queue.popleft()
11 next_node = edges[node]
12 if next_node != -1 and dist[next_node] == -1:
13 dist[next_node] = dist[node] + 1
14 queue.append(next_node)
15 return dist
16
17 def canMeet(self, dist1, dist2, n):
18 minDist = float('inf')
19 result = -1
20 for i in range(n):
21 if dist1[i] != -1 and dist2[i] != -1:
22 maxDist = max(dist1[i], dist2[i])
23 if maxDist < minDist:
24 minDist = maxDist
25 result = i
26 return result
27
28 def closestMeetingNode(self, edges, node1, node2):
29 n = len(edges)
30 dist1 = self.bfs(edges, node1)
31 dist2 = self.bfs(edges, node2)
32 return self.canMeet(dist1, dist2, n)This Python solution uses BFS to determine the shortest path from node1 and node2 to all nodes in the graph. After this, it calculates the minimum of the maximum distances encountered and returns the index of the node meeting the criteria.
Depth-First Search (DFS) can be leveraged to explore the graph while marking visited nodes to avoid cycles. This approach tracks distances from node1 and node2 in separate arrays, similarly to BFS but engages DFS mechanics.
Time Complexity: O(n) since every node is processed once.
Space Complexity: O(n) for the distance and visited sets.
1import
This Java solution employs DFS to determine distance arrays for nodes, clearing visits between runs. It identifies the best convergence node via optimal distance reductions.