#2359

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Find Closest Node to Given Two Nodes

Find the node that minimizes the maximum distance to two given nodes in a directed graph with one outgoing edge per node.

depth first search graph

Problem Statement

You are given a directed graph represented as an array edges where each element indicates a directed edge from node i to node edges[i]. If edges[i] == -1, node i has no outgoing edge. The graph has n nodes, numbered from 0 to n - 1, with at most one outgoing edge per node.

Given two nodes, node1 and node2, your task is to find the node that minimizes the maximum distance to both nodes. If multiple nodes have the same distance, return the smallest node index.

Examples

Example 1

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

Output: 2

The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1. The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.

Example 2

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

Output: 2

The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0. The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.

Constraints

n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n

Solution Approach

Graph Traversal

Start by performing a depth-first search (DFS) from both node1 and node2 to find the shortest path to all other nodes. This helps you map out distances from both nodes to all reachable nodes in the graph.

Compute Maximum Distances

After obtaining the distances, compute the maximum distance from each node to both node1 and node2. The node that minimizes the maximum distance is the closest node.

Return the Result

Finally, return the node that has the smallest maximum distance. If multiple nodes have the same maximum distance, return the node with the smallest index.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) due to the graph traversal via DFS, and the space complexity is O(n) as we store distances for each node in arrays.

What Interviewers Usually Probe

Look for knowledge of graph traversal algorithms, specifically DFS.
Test understanding of minimizing distances in a graph traversal context.
Check for efficiency in handling large graphs with the constraint of up to 100,000 nodes.

Common Pitfalls or Variants

Common pitfalls

Failing to handle graphs with nodes having no outgoing edges properly.
Not correctly calculating the maximum distance between two nodes.
Assuming that the closest node will always be a direct neighbor of either node1 or node2.

Follow-up variants

Consider graphs with more complex structures, like cycles or disconnected components.
Handle multiple test cases efficiently without redundant recalculation.
Extend the problem to find the closest node for multiple source nodes, not just two.

FAQ

What is the best algorithm for this problem?

A depth-first search (DFS) is effective for finding the shortest path in a graph where each node has at most one outgoing edge.

How do you handle nodes with no outgoing edges?

If a node has no outgoing edges, it is treated as having a distance of infinity from any other node unless it's the target node itself.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of nodes, because we perform DFS to calculate distances from two nodes.

What is the space complexity?

The space complexity is O(n) as we store the distances for each node in separate arrays.

How does GhostInterview help solve this problem?

GhostInterview provides detailed guidance on implementing DFS and calculating distances, helping you solve this problem efficiently and accurately.

terminal

Solution

Solution 1: BFS + Enumerate Common Nodes

We can first use BFS to calculate the distance from $node1$ and $node2$ to every node, denoted as $d_1$ and $d_2$ respectively. Then, enumerate all common nodes $i$, and for each, compute $\max(d_1[i], d_2[i])$. The answer is the node with the minimal such value.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        def f(i):
            dist = [inf] * n
            dist[i] = 0
            q = deque([i])
            while q:
                i = q.popleft()
                for j in g[i]:
                    if dist[j] == inf:
                        dist[j] = dist[i] + 1
                        q.append(j)
            return dist

        g = defaultdict(list)
        for i, j in enumerate(edges):
            if j != -1:
                g[i].append(j)
        n = len(edges)
        d1 = f(node1)
        d2 = f(node2)
        ans, d = -1, inf
        for i, (a, b) in enumerate(zip(d1, d2)):
            if (t := max(a, b)) < d:
                d = t
                ans = i
        return ans

Continue Practicing

#2360 longest cycle in a graph #2368 reachable nodes with restrictions #2328 number of increasing paths in a grid