#2359
Find Closest Node to Given Two Nodes
specialist · 845 · lc medium +31 · verified · 53% accepted · 2,097 likes · top 44%
Description
A directed graph has n nodes (labeled 0 to n - 1), each with at most one outgoing edge. The graph is encoded as a 0-indexed array edges of length n, where node i points to edges[i] (or has no outgoing edge if edges[i] == -1).
Given two node indices node1 and node2, find the node that both can reach such that the larger of the two distances (from node1 to it, and from node2 to it) is minimized. Return that node's index. On ties, return the smallest index. If no such node exists, return -1.
Note: 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.
Code
1
2
3