Watch 10 video solutions for Find Closest Node to Given Two Nodes, a medium level problem involving Depth-First Search, Graph. This walkthrough by codestorywithMIK has 12,008 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.
The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from i, then edges[i] == -1.
You are also given two integers node1 and node2.
Return the index of the node that can be reached from both node1 and node2, such that the maximum between the distance from node1 to that node, and from node2 to that node is minimized. If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1.
Note that edges may contain cycles.
Example 1:
Input: edges = [2,2,3,-1], node1 = 0, node2 = 1 Output: 2 Explanation: The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1. The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.
Example 2:
Input: edges = [1,2,-1], node1 = 0, node2 = 2 Output: 2 Explanation: The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0. The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.
Constraints:
n == edges.length2 <= n <= 105-1 <= edges[i] < nedges[i] != i0 <= node1, node2 < nProblem Overview: You are given a directed graph where each node has at most one outgoing edge. Starting from node1 and node2, find a node reachable from both such that the maximum of the two distances is minimized. If multiple nodes satisfy this condition, return the smallest index.
Approach 1: BFS for Shortest Path (O(n) time, O(n) space)
Treat the structure as a directed graph where each node points to at most one neighbor. Run a BFS (or simple forward traversal) from node1 to compute the shortest distance to every reachable node. Repeat the process from node2. After both distance arrays are built, iterate through all nodes and compute max(dist1[i], dist2[i]) for nodes reachable from both sources. Track the node with the smallest maximum distance and smallest index in case of ties. This works because BFS guarantees the shortest path in an unweighted graph.
This approach directly applies standard graph traversal techniques and is efficient since each node is processed at most once per traversal. With only one outgoing edge per node, the traversal behaves almost like following linked lists, keeping the runtime linear.
Approach 2: DFS for Shortest Path and Avoiding Cycles (O(n) time, O(n) space)
Use Depth-First Search to explore paths starting from each source node while tracking distances. Maintain a visited set or distance array to avoid revisiting nodes, which prevents infinite loops caused by cycles. Each recursive call records the current distance before moving to the next neighbor defined by edges[i]. After computing distance arrays for both starting nodes, scan through all nodes and select the one minimizing max(dist1[i], dist2[i]).
DFS works well because every node has only one outgoing edge, so the recursion path is straightforward and cycle detection is easy. The algorithm still processes each node at most once per traversal, keeping the complexity linear.
Recommended for interviews: The BFS-style traversal is typically preferred because it explicitly models shortest paths in an unweighted graph. It is easier to reason about distances and avoids recursion overhead. Showing the DFS variant demonstrates understanding of DFS and cycle handling, but interviewers usually expect the linear shortest-distance approach.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS for Shortest Path | O(n) | O(n) | Best general solution for shortest distance in an unweighted directed graph |
| DFS with Cycle Avoidance | O(n) | O(n) | Useful when implementing recursive traversal or explicitly handling cycles |