Choose a Shared Reachable Node Minimizing the Worse Distance
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A directed graph has nodes `0` through `n - 1`, each with at most one outgoing edge. `edges[i]` is its destination, or `-1` if there is none. Find a node reachable from both `node1` and `node2` that minimizes the larger of their two shortest distances to it. Break ties by smaller node index. Return `-1` if no common reachable node exists. A node reaches itself at distance zero.
```cpp
class Solution {
public:
int closestMeetingNode(vector<int>& edges, int node1, int node2);
};
```
### Examples
**Example 1:**
```text
Input: edges = [1,2,0], node1 = 0, node2 = 1
Output: 1
Explanation: Node 1 has distances 1 and 0. Nodes 0 and 2 each have a larger maximum distance of 2.
```
**Example 2:**
```text
Input: edges = [-1,-1], node1 = 0, node2 = 1
Output: -1
Explanation: Each start is isolated and cannot reach the other, so no common reachable node exists.
```
### Constraints
- `2 <= edges.length <= 100000`.
- `-1 <= edges[i] < n`, and `edges[i] != i`.
- `0 <= node1, node2 < n`; cycles may exist.
### Clarifying Questions
- Are edges directed? Yes; you cannot follow them backward.
- Can the graph contain cycles? Yes.
- Which distance is minimized? The larger of the two distances to the same candidate node.
- What breaks ties? The smallest node index.
```hint Check the boundary
Compare candidates using the larger distance, rather than adding the two distances.
```
Overview: Choose a node reachable from two starts that minimizes their maximum directed distance, with smallest-index tie breaking.
