LeetCode 2359 - Find Closest Node to Given Two Nodes

The problem asks us to find a node in a directed graph with a very specific property: it must be reachable from two given starting nodes (node1 and node2) such that the maximum distance from either starting node to this node is minimized.

leetcodemediumdepth-first-searchgraph-theory

LeetCode Problem 2359

Difficulty: 🟡 Medium
Topics: Depth-First Search, Graph Theory

Solution

Problem Understanding

The problem asks us to find a node in a directed graph with a very specific property: it must be reachable from two given starting nodes (node1 and node2) such that the maximum distance from either starting node to this node is minimized. The graph is described by an array edges where edges[i] is the node that i points to, or -1 if there is no outgoing edge. Each node has at most one outgoing edge, so the graph consists of chains and cycles.

The input is a single array edges of length n and two integers representing the starting nodes. The output is the index of the node that satisfies the minimum-maximum distance criterion. If multiple nodes tie, we return the one with the smallest index. If no such node exists (the two starting nodes cannot reach a common node), we return -1.

Constraints indicate that n can be up to 10^5, so O(n^2) algorithms will not scale. The graph's structure-at most one outgoing edge per node-suggests that simple linear traversals from each node can be efficient.

Important edge cases include situations where a starting node points to -1 immediately, or when cycles exist. We also need to handle nodes that are reachable from only one of the two starting points.

Approaches

Brute Force

A naive approach would involve computing the distance from node1 to every other node and from node2 to every other node using BFS or DFS. For each node reachable from both, we would compute the maximum distance and pick the node with the smallest maximum. While correct, this is inefficient because repeatedly traversing paths from each starting node can result in O(n^2) time complexity in the worst case for long chains.

Optimal Approach

The optimal observation is that each node has at most one outgoing edge, so the distance from a node to all reachable nodes can be computed in linear time by walking the chain once. We can compute two arrays, dist1 and dist2, where dist1[i] is the distance from node1 to i, and dist2[i] is the distance from node2 to i. If a node is unreachable from a starting node, we mark the distance as -1 or infinity. Then we iterate through all nodes and compute the maximum distance from the two arrays for nodes reachable from both. The answer is the node with the minimum of these maximums.

This works efficiently because each node is visited at most once per starting node, resulting in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Compute distances to all nodes repeatedly
Optimal O(n) O(n) Use linear traversal from each node and store distances

Algorithm Walkthrough

  1. Initialize two distance arrays dist1 and dist2 of length n, filled with -1 to indicate nodes not yet reached.
  2. Define a helper function walk(start) that traverses the graph starting from start. For each visited node, record the distance in an array and stop when reaching a node already visited or -1.
  3. Call walk(node1) and store distances in dist1.
  4. Call walk(node2) and store distances in dist2.
  5. Initialize variables minMaxDist as infinity and answer as -1.
  6. Iterate through all nodes from 0 to n-1. If a node is reachable from both (dist1[i] != -1 and dist2[i] != -1), compute max(dist1[i], dist2[i]). If this value is smaller than minMaxDist, update minMaxDist and set answer to this node. If equal, choose the smaller index.
  7. Return answer.

Why it works: The algorithm ensures that all reachable nodes from each start are considered exactly once. The min-max comparison ensures that the node chosen minimizes the maximum distance from both starting points. Lexicographical tie-breaking is automatically handled by iterating in order of indices.

Python Solution

from typing import List

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        
        def walk(start):
            dist = [-1] * n
            current = start
            steps = 0
            while current != -1 and dist[current] == -1:
                dist[current] = steps
                steps += 1
                current = edges[current]
            return dist
        
        dist1 = walk(node1)
        dist2 = walk(node2)
        
        minMaxDist = float('inf')
        answer = -1
        
        for i in range(n):
            if dist1[i] != -1 and dist2[i] != -1:
                maxDist = max(dist1[i], dist2[i])
                if maxDist < minMaxDist:
                    minMaxDist = maxDist
                    answer = i
        return answer

Implementation Walkthrough: We define walk to traverse from a starting node, marking distances. We then walk from both node1 and node2. Iterating over all nodes allows us to select the one that minimizes the maximum distance from both starting nodes, and iterating in order ensures smallest index tie-breaking.

Go Solution

func closestMeetingNode(edges []int, node1 int, node2 int) int {
    n := len(edges)
    
    walk := func(start int) []int {
        dist := make([]int, n)
        for i := 0; i < n; i++ {
            dist[i] = -1
        }
        current := start
        steps := 0
        for current != -1 && dist[current] == -1 {
            dist[current] = steps
            steps++
            current = edges[current]
        }
        return dist
    }
    
    dist1 := walk(node1)
    dist2 := walk(node2)
    
    minMaxDist := 1 << 60
    answer := -1
    
    for i := 0; i < n; i++ {
        if dist1[i] != -1 && dist2[i] != -1 {
            maxDist := dist1[i]
            if dist2[i] > maxDist {
                maxDist = dist2[i]
            }
            if maxDist < minMaxDist {
                minMaxDist = maxDist
                answer = i
            }
        }
    }
    
    return answer
}

Go-specific notes: We initialize dist with -1 using a loop since Go does not allow slices to have default values other than zero. Integer overflow is avoided by using a large constant 1 << 60.

Worked Examples

Example 1: edges = [2,2,3,-1], node1 = 0, node2 = 1

Walking from node1:

0 -> 2 -> 3 -> -1
dist1 = [0, -1, 1, 2]

Walking from node2:

1 -> 2 -> 3 -> -1
dist2 = [-1, 0, 1, 2]

Iterating nodes:

  • Node 0: not reachable from node2
  • Node 1: not reachable from node1
  • Node 2: reachable, max(1,1) = 1 → answer = 2
  • Node 3: reachable, max(2,2) = 2 → larger than current minMaxDist → ignored

Answer = 2.

Example 2: edges = [1,2,-1], node1 = 0, node2 = 2

Walking from node1:

0 -> 1 -> 2 -> -1
dist1 = [0,1,2]

Walking from node2:

2 -> -1
dist2 = [-1,-1,0]

Iterating nodes:

  • Node 2: reachable from both, max(2,0) = 2 → answer = 2

Answer = 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited at most once per starting node during walk and once during final iteration
Space O(n) Two distance arrays of size n are used

The linear time is guaranteed because the graph has at most one outgoing edge per node.

Test Cases

# provided examples
assert Solution().closestMeetingNode([2,2,3,-1], 0, 1) == 2
assert Solution().closestMeetingNode([1,2,-1], 0, 2) == 2

# edge cases
assert Solution().closestMeetingNode([-1,-1], 0, 1) == -1  # no reachable common node
assert Solution().closestMeetingNode([1,-1], 0, 0) == 0    # same node for both
assert Solution().closestMeetingNode([1,2,3,4,-1], 0, 2) == 2 # chain intersection
Test Why
[2,2,3,-1], 0, 1