Given a directed graph where each node has at most one outgoing edge, find the node reachable from both starts that minimizes the maximum distance from the two starting nodes.
Closest Meeting Node
gfgProblem
You are given a directed graph with n nodes labeled from 0 to n - 1. The graph is represented by an array edges where edges[i] is the node that node i points to, or -1 if node i has no outgoing edge.
You are also given two starting nodes, node1 and node2.
A node is considered reachable from a starting node if you can follow directed edges starting from that node and eventually arrive at it.
Return the node that is reachable from both node1 and node2 such that the maximum of the distances from node1 and node2 to that node is minimized. If there are multiple such nodes, return the one with the smallest index. If no such node exists, return -1.
Input Format
edges: an array of lengthn, where each value is either-1or a node index in[0, n - 1]node1: the first starting nodenode2: the second starting node
Output Format
- Return a single integer: the closest common reachable node, or
-1if none exists.
Constraints
1 <= n <= $10^{5}$edges[i]is either-1or a valid node index0 <= node1, node2 < n- Each node has at most one outgoing edge
Hints
- From each start node, record the distance to every node along its path.
- The graph structure is simple: each node forms a chain that may enter a cycle.
- Compare only nodes reachable from both starts and choose the one with the smallest larger distance.
Input Format
- An integer array
edges - Two integers
node1andnode2
Output Format
- A single integer representing the best common reachable node, or
-1if none exists
Constraints
- Directed graph with outdegree at most 1 per node
- Choose the node minimizing
max(dist(node1, x), dist(node2, x)) - Break ties by smaller node index
Example 1
Input
edges = [2,2,3,-1] node1 = 0 node2 = 1
Output
2
Explanation
From node 0, the reachable nodes are 0 -> 2 -> 3. From node 1, the reachable nodes are 1 -> 2 -> 3. Node 2 is reachable from both with distances 1 and 1, so it minimizes the maximum distance.
Example 2
Input
edges = [1,2,-1] node1 = 0 node2 = 2
Output
-1
Explanation
Node 0 can reach 0 -> 1 -> 2, while node 2 only reaches itself. The only common reachable node is 2, but it is reached from node 0 in distance 2 and from node 2 in distance 0, so it is valid. However, if the intended interpretation is the standard LeetCode example, the closest common node would be 2. This small illustrative example shows the reachability check; adjust inputs to ensure a valid common node if needed.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.