[Leetcode] 2359. Find Closest Node to Given Two Nodes

https://leetcode.com/problems/find-closest-node-to-given-two-nodes/description/?envType=daily-question&envId=2025-05-30

initial

so i didnt understand the condition. Dafuq is this minimum of maximum distances?

So q is asking:
from node1 to node2, we can have some common nodes that can be traversed. From node1 and node2 to common node, lets say dist1 and dist2. We need to get the max(dist1,dist2) and this maximum value has to be the minimum possible. Like if common nods are 2 and 3 and the maximum value is like 5 and 9, 5 is the min possible. Then we have to return node 2, not value 5. So we have to keep track of which common node has this smallest value.

my way

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        graph=[[] for _ in range(n)]
        for i in range(n):
            end = edges[i]
            if end==-1:
                continue
            graph[i].append(end)
        visited1,visited2=set(),set()
        dist1,dist2=[0 for _ in range(n)], [0 for _ in range(n)]
        def dfs(node,graph,visited,dist, depth):
            if node not in visited:
                visited.add(node)
            dist[node]=depth
            for neigh in graph[node]:
                if neigh not in visited:
                    dfs(neigh,graph,visited,dist, depth+1)
        dfs(node1,graph,visited1,dist1,0)
        dfs(node2,graph,visited2,dist2,0)

        common= visited1 & visited2
        print(common)

        ans = int(10e18)
        hola = -1
        com = sorted(list(common))
        for i in com:
            a,b=dist1[i],dist2[i]
            if min(ans, max(a,b))==ans:
                continue
            hola=i
            ans = min(ans, max(a,b))
        return -1 if ans==int(10e18) else hola

sol (better time with bfs)

actually generally dfs time is worse than bfs. We dont even need to create a graph 2d list. If we just create a 1d distance list from node1 and another for node2 and fill the distances along with bfs like

                # If there's an outgoing edge and we haven't visited the next node
                if next_node != -1 and distances[next_node] == -1:

this is much better and also we dont have to do the sort which is n log n
we also dont explicitly need visited list cuz dist can be initialised as -1 for each indexes.

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        
        def bfs_distances(start):
            """BFS to find distances from start node to all reachable nodes"""
            distances = [-1] * n  # -1 means unreachable
            queue = [start]
            distances[start] = 0
            
            while queue:
                node = queue.pop(0)
                next_node = edges[node]
                
                # If there's an outgoing edge and we haven't visited the next node
                if next_node != -1 and distances[next_node] == -1:
                    distances[next_node] = distances[node] + 1
                    queue.append(next_node)
            
            return distances
        
        # Get distances from both starting nodes
        dist1 = bfs_distances(node1)
        dist2 = bfs_distances(node2)
        
        # Find the closest meeting node
        min_max_dist = float('inf')
        result = -1
        
        for i in range(n):
            # Check if node i is reachable from both starting nodes
            if dist1[i] != -1 and dist2[i] != -1:
                max_dist = max(dist1[i], dist2[i])
                # Update result if we found a better option
                # In case of tie, choose smaller index (since we iterate from 0)
                if max_dist < min_max_dist:
                    min_max_dist = max_dist
                    result = i
        
        return result

complexity

dfs = n + n log n
bfs = n

space is both n