Find Closest Node to Given Two Nodes
Medium · Graphs · Explanation and code example
Iterative Depth First Search
How it works
Since each node has exactly one outgoing edge, we can replace recursion with a simple while loop. Starting from each source, we follow edges iteratively until we reach -1 or a visited node. This avoids recursion overhead while computing the same distances.
Steps
- For each source node, initialize its distance to
0. - Iteratively follow
edges[node]while the neighbor exists and is unvisited:- Set the neighbor's distance to current
distance + 1. - Move to the neighbor.
- Set the neighbor's distance to current
- Repeat for both
node1andnode2. - Find the node minimizing
max(node1Dist[i], node2Dist[i])among doubly-reachable nodes. - Return the result.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Using Sum Instead of Maximum Distance
The problem asks for the node that minimizes the maximum of the two distances, not the sum. Using node1Dist[i] + node2Dist[i] instead of max(node1Dist[i], node2Dist[i]) produces incorrect results.
Not Handling Cycles Properly
The graph can contain cycles, so distance computation must mark visited nodes to avoid infinite loops. Always check if a node has already been assigned a distance before processing it.
Forgetting to Return the Smallest Index on Ties
When multiple nodes have the same minimum maximum distance, the problem requires returning the smallest index. Iterating from index 0 and using strict less-than comparison ensures the first valid node is selected.
Python code example
class Solution:
def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:
n = len(edges)
def dfs(node):
dist = [-1] * n
dist[node] = 0
while edges[node] != -1 and dist[edges[node]] == -1:
nei = edges[node]
dist[nei] = dist[node] + 1
node = nei
return dist
node1Dist, node2Dist = dfs(node1), dfs(node2)
res, resDist = -1, float("inf")
for i in range(n):
if min(node1Dist[i], node2Dist[i]) != -1:
dist = max(node1Dist[i], node2Dist[i])
if dist < resDist:
resDist, res = dist, i
return res
C++ code example
class Solution {
public:
int closestMeetingNode(vector<int>& edges, int node1, int node2) {
int n = edges.size();
vector<int> node1Dist = dfs(node1, edges, n);
vector<int> node2Dist = dfs(node2, edges, n);
int res = -1, resDist = INT_MAX;
for (int i = 0; i < n; i++) {
if (min(node1Dist[i], node2Dist[i]) != -1) {
int dist = max(node1Dist[i], node2Dist[i]);
if (dist < resDist) {
resDist = dist;
res = i;
}
}
}
return res;
}
private:
vector<int> dfs(int node, vector<int>& edges, int n) {
vector<int> dist(n, -1);
dist[node] = 0;
while (edges[node] != -1 && dist[edges[node]] == -1) {
int nei = edges[node];
dist[nei] = dist[node] + 1;
node = nei;
}
return dist;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.