Find Closest Node to Given Two Nodes

main.md

Question

Approach

To solve this, I first compute the distances from node1 and node2 to all other nodes using a simple traversal, since each node has at most one outgoing edge. I record these distances in two separate arrays. Then, I iterate through all nodes to find the ones that are reachable from both node1 and node2. For each such node, I calculate the maximum of the two distances and keep track of the node with the smallest such maximum. If there’s a tie, I pick the node with the smaller index.

Implementation

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        def get_distances(start):
            dist = [-1] * len(edges)
            d = 0
            while start != -1 and dist[start] == -1:
                dist[start] = d
                start = edges[start]
                d += 1
            return dist

        dist1 = get_distances(node1)
        dist2 = get_distances(node2)

        min_dist = float('inf')
        answer = -1

        for i in range(len(edges)):
            if dist1[i] != -1 and dist2[i] != -1:
                max_d = max(dist1[i], dist2[i])
                if max_d < min_dist:
                    min_dist = max_d
                    answer = i
        return answer

Complexities

• Time: O(n)
• Space: O(n)