Problem

You are also given two integers node1 and node2.

Return the index of the node that can be reached from both node1 and node2, such that the maximum between the distance from node1 to that node, and from node2 to that node is minimized. If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1.

Note that edges may contain cycles.

Examples

Example 1:

graph TD
  0 --> 2
  1 --> 2
  2 --> 3
  
1
2
3
4

Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Explanation: 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:

graph LR
  0 --> 1
  1 --> 2
  
1
2
3
4

Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Explanation: 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.

Solution

Method 1 - Using BFS or single source shortest path

This problem involves finding a node that can be reached from both node1 and node2 with distances that balance minimisation and maximisation properties. To achieve this efficiently, we perform a breadth-first search (BFS) or single-source shortest path traversal starting from both nodes, capturing the distances to all reachable nodes.

Approach

  1. Graph Representation:
    • The edges array defines a graph where the index is the node, and the value at the index is the next node it points to.
    • This is essentially a directed graph (may contain cycles).
  2. Distance Calculation:
    • Use BFS or a similar traversal to compute the distance of each node from node1 and node2.
  3. Finding the Optimum Node:
    • For each node reachable by both node1 and node2, compute the maximum distance (max(dist1[node], dist2[node])) and track the minimum of these values.
    • In case of ties, return the node with the smallest index.
  4. Edge Cases:
    • If no node is reachable by both node1 and node2, return -1.

Code

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] dist1 = new int[n];
        int[] dist2 = new int[n];
        
        // Fill all distances with a sufficiently large value
        java.util.Arrays.fill(dist1, Integer.MAX_VALUE);
        java.util.Arrays.fill(dist2, Integer.MAX_VALUE);
        
        // BFS helper to calculate distances
        calculateDistances(edges, node1, dist1);
        calculateDistances(edges, node2, dist2);
        
        int ans = -1;
        int minDistance = Integer.MAX_VALUE;
        
        // Find the minimum distance node reachable by both
        for (int i = 0; i < n; i++) {
            if (dist1[i] != Integer.MAX_VALUE && dist2[i] != Integer.MAX_VALUE) {
                int maxDist = Math.max(dist1[i], dist2[i]);
                if (maxDist < minDistance || (maxDist == minDistance && i < ans)) {
                    ans = i;
                    minDistance = maxDist;
                }
            }
        }
        return ans;
    }
    
    private void calculateDistances(int[] edges, int start, int[] dist) {
        int n = edges.length;
        boolean[] visited = new boolean[n];
        int d = 0;
        while (start != -1 && !visited[start]) {
            dist[start] = d++;
            visited[start] = true;
            start = edges[start];
        }
    }
}
 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
28
29
30

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        dist1 = [float('inf')] * n
        dist2 = [float('inf')] * n
        
        def calculate_distances(start: int, dist: List[int]) -> None:
            visited = [False] * n
            d = 0
            while start != -1 and not visited[start]:
                dist[start] = d
                visited[start] = True
                d += 1
                start = edges[start]
        
        # Calculate distances
        calculate_distances(node1, dist1)
        calculate_distances(node2, dist2)
        
        ans = -1
        min_distance = float('inf')
        
        # Find the minimum distance node reachable by both
        for i in range(n):
            if dist1[i] != float('inf') and dist2[i] != float('inf'):
                max_dist = max(dist1[i], dist2[i])
                if max_dist < min_distance or (max_dist == min_distance and i < ans):
                    ans = i
                    min_distance = max_dist
        return ans

Complexity

  • ⏰ Time complexity: O(n)
    • O(n) for graph traversal (BFS or shortest-path) for both node1 and node2.
    • O(n) for selecting the optimum node.
    • Total complexity is O(n) where n is the number of nodes.
  • 🧺 Space complexity: O(n), for using arrays to store distances from both sources: O(n).