Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every node has at most one outgoing edge, so following edges from a start gives its unique reachable route until a dead end or cycle. Distances from the two starts can be computed independently, then compared at every common reachable node.

Approach

Traverse from each starting node, recording distance zero at the start and increasing it along edges; visited tracking stops cycles. Scan node IDs in increasing order. For nodes reached from both starts, evaluate the larger of the two distances and update the answer only when it strictly improves. This minimizes the required maximum distance, while the increasing-ID scan preserves the smaller identifier on ties. Return -1 if no common reachable node exists.

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        adj = defaultdict(list)

        for i in range(n):
            if edges[i] == -1:
                continue
            adj[i].append(edges[i])

        def dfs(i):
            s = [(i, -1)] # node, dist
            distances = {}
            seen = set()
            seen.add(i)

            while s:
                node, dist = s.pop()
                distances[node] = dist + 1
                for nei in adj[node]:
                    if not nei in seen:
                        seen.add(nei)
                        s.append((nei, dist + 1))

            return distances

        map1 = dfs(node1)
        map2 = dfs(node2)
        res = float('inf')
        selected = -1

        for i in range(n):
            if i in map1 and i in map2:
                mx = max(map1[i], map2[i])
                if mx < res:
                    res = mx
                    selected = i

        return selected

Complexity analysis

Let n = edges.length. Time: O(n) to walk from both start nodes and scan all possible meeting nodes. Auxiliary space: O(n) for adjacency/distance/visited state.