[Graph] LeetCode 2359. Find Closest Node to Given Two Nodes

Solution BFS

from collections import deque

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        min_dist, res = int(1e9), -1

        graph = [[] for _ in range(n)]
        distance1 = [int(1e9)] * n
        distance2 = [int(1e9)] * n

        distance1[node1] = 0
        distance2[node2] = 0

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

        def bfs(v, node_type):
            q = deque([(v,0)])
            visited = [False] * n
            visited[v] = True

            while q:
                cur_node, distance = q.popleft()

                for neigh in graph[cur_node]:
                    if not visited[neigh]:
                        visited[neigh] = True
                        if node_type == "node1":
                            distance1[neigh] = distance + 1
                        else:
                            distance2[neigh] = distance + 1
                        q.append((neigh, distance + 1))

        bfs(node1, "node1")
        bfs(node2, "node2")

        for i in range(n):
            if distance1[i] != int(1e9) and distance2[i] != int(1e9):
                max_dist = max(distance1[i], distance2[i])
                if min_dist > max_dist:
                    min_dist = max_dist
                    res = i

        return res

This problem can be solved using both BFS and DFS, because each node has at most one outgoing edge.

1. Create an adjacency list named graph, to store the directly connected nodes for each node. Do not store the edges that has a value of -1.
2. Create a distance array for node1 and node2. This is used to calculate the distance to all other nodes for each node1 and node2.
3. Set distance1[node1] = 0 and distance2[node2] = 0 since they are the starting nodes.
4. Run BFS for both node1 / node2 and update the distance array.
5. Check if both node1 and node2 can reach a certain node, and find the index having the minimum distance.