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.
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.
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.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) since each node is processed in the queue at most once.
Space Complexity: O(n) for storing distances.
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.
This Python solution uses DFS to explore graphs from two nodes, calculating visiting distances and determining the optimal meeting node that minimizes the maximal distance.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) since every node is processed once.
Space Complexity: O(n) for the distance and visited sets.
We can first use BFS to calculate the distance from node1 and node2 to every node, denoted as d_1 and d_2 respectively. Then, enumerate all common nodes i, and for each, compute max(d_1[i], d_2[i]). The answer is the node with the minimal such value.
The complexity is O(n), and the space complexity is O(n), where n is the number of nodes.
Related problems:
| Approach | Complexity |
|---|---|
| Approach 1: BFS for Shortest Path | Time Complexity: O(n) since each node is processed in the queue at most once. |
| Approach 2: DFS for Shortest Path and Avoiding Cycles | Time Complexity: O(n) since every node is processed once. |
| BFS + Enumerate Common Nodes | — |
| 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 |
Find Closest Node to Given Two Nodes | BFS | DFS | Leetcode 2359 | codestorywithMIK • codestorywithMIK • 12,008 views views
Watch 9 more video solutions →Practice Find Closest Node to Given Two Nodes with our built-in code editor and test cases.
Practice on FleetCode