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.
1var closestMeetingNode = function(edges, node1, node2) {
2 const bfs = (start) => {
3 const n = edges.length;
4 const dist = new Array(n).fill(-1);
5 const queue = [start];
6 dist[start] = 0;
7 while (queue.length > 0) {
8 const node = queue.shift();
9 const nextNode = edges[node];
10 if (nextNode !== -1 && dist[nextNode] === -1) {
11 dist[nextNode] = dist[node] + 1;
12 queue.push(nextNode);
13 }
14 }
15 return dist;
16 }
17
18 const n = edges.length;
19 const dist1 = bfs(node1);
20 const dist2 = bfs(node2);
21
22 let minDist = Infinity;
23 let result = -1;
24 for (let i = 0; i < n; i++) {
25 if (dist1[i] !== -1 && dist2[i] !== -1) {
26 const maxDist = Math.max(dist1[i], dist2[i]);
27 if (maxDist < minDist) {
28 minDist = maxDist;
29 result = i;
30 }
31 }
32 }
33 return result;
34};This JavaScript implementation applies BFS from the starting nodes to compute shortest distances. By determining the node with the minimum maximum distance, it efficiently identifies the solution.
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.
1#include <vector>
2#include <unordered_set>
#include <limits.h>
class Solution {
public:
void dfs(std::vector<int>& edges, int start, std::vector<int>& dist, std::unordered_set<int>& visited) {
int node = start;
int distance = 0;
while (node != -1 && visited.find(node) == visited.end()) {
visited.insert(node);
dist[node] = distance;
node = edges[node];
++distance;
}
}
int closestMeetingNode(std::vector<int>& edges, int node1, int node2) {
int n = edges.size();
std::vector<int> dist1(n, -1), dist2(n, -1);
std::unordered_set<int> visited;
dfs(edges, node1, dist1, visited);
visited.clear();
dfs(edges, node2, dist2, visited);
int minDist = INT_MAX;
int result = -1;
for (int i = 0; i < n; ++i) {
if (dist1[i] != -1 && dist2[i] != -1) {
int maxDist = std::max(dist1[i], dist2[i]);
if (maxDist < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
}
};This C++ implementation uses DFS to compute shortest paths by depth-first exploration and calculates the optimal node by minimizing overlapping path distances.