2359. Find Closest Node to Given Two Nodes - Explanation

Problem Link



Intuition

We want a node reachable from both node1 and node2 that minimizes the maximum of the two distances. First, we compute distances from node1 to all reachable nodes, then do the same from node2. For each node reachable from both, the "cost" is the larger of the two distances. We pick the node with the smallest such cost, breaking ties by choosing the smaller index.

Algorithm

  1. Build an adjacency list from the edges array.
  2. Run BFS from node1 to compute distances to all reachable nodes, storing them in node1Dist.
  3. Run BFS from node2 to compute distances, storing them in node2Dist.
  4. Iterate through all nodes. For each node reachable from both sources:
    • Compute dist = max(node1Dist[i], node2Dist[i]).
    • If this is smaller than the best seen so far, update the result.
  5. Return the best node index, or -1 if none exists.
class Solution:
    def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:
        adj = defaultdict(list)
        for i, nei in enumerate(edges):
            adj[i].append(nei)

        def bfs(src, distMap):
            q = deque([(src, 0)])
            distMap[src] = 0
            while q:
                node, dist = q.popleft()
                for nei in adj[node]:
                    if nei not in distMap:
                        q.append((nei, dist + 1))
                        distMap[nei] = dist + 1

        node1Dist, node2Dist = {}, {}
        bfs(node1, node1Dist)
        bfs(node2, node2Dist)

        res, resDist = -1, float("inf")
        for i in range(len(edges)):
            if i in node1Dist and i in node2Dist:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i

        return res

Time & Space Complexity

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

2. Breadth First Search (Optimal)

Intuition

Since each node has at most one outgoing edge, we do not need a full adjacency list. We can traverse directly using the edges array. The BFS logic remains the same, but we simplify by following edges[node] directly instead of iterating through neighbors.

Algorithm

  1. Run BFS from node1: follow edges[node] until we hit -1 or revisit a node, recording distances in node1Dist.
  2. Run BFS from node2 the same way, storing results in node2Dist.
  3. Scan all nodes. For each one reachable from both sources, track the minimum of max(node1Dist[i], node2Dist[i]).
  4. Return the node with the smallest maximum distance, or -1 if unreachable.
class Solution:
    def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:
        n = len(edges)

        def bfs(src):
            dist = [-1] * n
            q = deque([src])
            dist[src] = 0

            while q:
                node = q.popleft()
                nei = edges[node]
                if nei == -1 or dist[nei] >= 0:
                    continue
                q.append(nei)
                dist[nei] = dist[node] + 1
            return dist

        node1Dist, node2Dist = bfs(node1), bfs(node2)

        res, resDist = -1, float("inf")
        for i in range(n):
            if node1Dist[i] != -1 and node2Dist[i] != -1:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i

        return res

Time & Space Complexity

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

Intuition

DFS achieves the same goal as BFS here. Starting from each source node, we recursively follow edges and record distances. The graph structure (each node has at most one outgoing edge) means DFS naturally follows the single path from each source without branching.

Algorithm

  1. Initialize distance arrays node1Dist and node2Dist with -1 (unreachable).
  2. Set node1Dist[node1] = 0 and node2Dist[node2] = 0.
  3. Run DFS from node1: for each unvisited neighbor, set its distance and recurse.
  4. Run DFS from node2 similarly.
  5. Find the node with the minimum value of max(node1Dist[i], node2Dist[i]) among nodes reachable from both.
  6. Return that node, or -1 if none.
class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)

        def dfs(node, dist):
            nei = edges[node]
            if nei != -1 and dist[nei] == -1:
                dist[nei] = dist[node] + 1
                dfs(nei, dist)

        node1Dist = [-1] * n
        node2Dist = [-1] * n
        node1Dist[node1] = node2Dist[node2] = 0

        dfs(node1, node1Dist)
        dfs(node2, node2Dist)

        res, resDist = -1, float("inf")
        for i in range(n):
            if min(node1Dist[i], node2Dist[i]) != -1:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i

        return res

Time & Space Complexity

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

Intuition

Since each node has exactly one outgoing edge, we can replace recursion with a simple while loop. Starting from each source, we follow edges iteratively until we reach -1 or a visited node. This avoids recursion overhead while computing the same distances.

Algorithm

  1. For each source node, initialize its distance to 0.
  2. Iteratively follow edges[node] while the neighbor exists and is unvisited:
    • Set the neighbor's distance to current distance + 1.
    • Move to the neighbor.
  3. Repeat for both node1 and node2.
  4. Find the node minimizing max(node1Dist[i], node2Dist[i]) among doubly-reachable nodes.
  5. Return the result.
class Solution:
    def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:
        n = len(edges)

        def dfs(node):
            dist = [-1] * n
            dist[node] = 0
            while edges[node] != -1 and dist[edges[node]] == -1:
                nei = edges[node]
                dist[nei] = dist[node] + 1
                node = nei
            return dist

        node1Dist, node2Dist = dfs(node1), dfs(node2)
        res, resDist = -1, float("inf")
        for i in range(n):
            if min(node1Dist[i], node2Dist[i]) != -1:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i
        return res

Time & Space Complexity

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

Common Pitfalls

Using Sum Instead of Maximum Distance

The problem asks for the node that minimizes the maximum of the two distances, not the sum. Using node1Dist[i] + node2Dist[i] instead of max(node1Dist[i], node2Dist[i]) produces incorrect results.

Not Handling Cycles Properly

The graph can contain cycles, so distance computation must mark visited nodes to avoid infinite loops. Always check if a node has already been assigned a distance before processing it.

Forgetting to Return the Smallest Index on Ties

When multiple nodes have the same minimum maximum distance, the problem requires returning the smallest index. Iterating from index 0 and using strict less-than comparison ensures the first valid node is selected.