# Find Closest Node to Given Two Nodes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-closest-node-to-given-two-nodes)
Canonical: https://scaleengineer.com/dsa/problems/find-closest-node-to-given-two-nodes
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Graph
**Companies:** [Juspay](https://scaleengineer.com/companies/juspay)
---
## Problem
You are given a **directed** graph of `n` nodes numbered from `0` to `n - 1`, where each node has **at most one** outgoing edge.

The graph is represented with a given **0-indexed** array `edges` of size `n`, indicating that there is a directed edge from node `i` to node `edges[i]`. If there is no outgoing edge from `i`, then `edges[i] == -1`.

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.

**Example 1:**

![](https://assets.glich.co/dsa/find-closest-node-to-given-two-nodes/image0.png) 

**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:**

![](https://assets.glich.co/dsa/find-closest-node-to-given-two-nodes/image1.png) 

**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.

**Constraints:**

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

# Approaches
## Brute Force by Checking Each Node
This approach iterates through every node in the graph, treating each one as a potential meeting point. For each potential meeting node, it calculates the distance from `node1` and `node2` by performing separate traversals from each starting node. It then keeps track of the node that minimizes the maximum of these two distances.
**Time:** O(n^2) - The main loop runs `n` times. Inside the loop, the `getDistance` helper function can traverse up to `n` nodes in the worst case. This results in a quadratic time complexity. · **Space:** O(n) - The `getDistance` function uses a `visited` boolean array of size `n` to handle cycles. This array is re-created for each call within the main loop.
**Pros:** Conceptually straightforward and easy to understand.
**Cons:** Highly inefficient due to redundant computations for each potential meeting node.; Very likely to result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
The core idea is to test all possibilities. We can write a helper function, `getDistance(start, end, edges)`, that finds the shortest path distance from a `start` node to an `end` node. This function would traverse the graph from `start`, keeping track of the distance, until it either reaches `end`, a dead end (`-1`), or a cycle. To handle cycles, a `visited` array is necessary within this helper function.

The main function then iterates through all nodes `i` from `0` to `n-1`. For each `i`, it calls `getDistance(node1, i, ...)` and `getDistance(node2, i, ...)`. If node `i` is reachable from both, it computes the maximum of the two distances. This maximum distance is compared with the minimum one found so far. If the current node `i` offers a strictly smaller maximum distance, it becomes the new best candidate. If the distances are equal, the node with the smaller index is preferred, which is naturally handled by iterating `i` in increasing order.

```java
class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int minMaxDist = Integer.MAX_VALUE;
        int resultNode = -1;

        for (int i = 0; i < n; i++) {
            int d1 = getDistance(node1, i, edges);
            if (d1 != -1) {
                int d2 = getDistance(node2, i, edges);
                if (d2 != -1) {
                    int maxDist = Math.max(d1, d2);
                    if (maxDist < minMaxDist) {
                        minMaxDist = maxDist;
                        resultNode = i;
                    }
                }
            }
        }
        return resultNode;
    }

    private int getDistance(int startNode, int endNode, int[] edges) {
        int dist = 0;
        int currNode = startNode;
        boolean[] visited = new boolean[edges.length];

        while (currNode != -1 && !visited[currNode]) {
            if (currNode == endNode) {
                return dist;
            }
            visited[currNode] = true;
            currNode = edges[currNode];
            dist++;
        }
        return -1;
    }
}
```
### Algorithm
* Initialize `min_max_dist` to `Integer.MAX_VALUE` and `result_node` to -1.
* Loop through each node `i` from `0` to `n-1` to consider it as a potential meeting node.
* Inside the loop, define a helper function `getDistance(start, end, edges)` to calculate the distance from a `start` node to an `end` node.
*   This helper function traverses from `start`, incrementing a distance counter. It uses a `visited` array to detect and handle cycles, preventing infinite loops.
*   If `end` is reached, it returns the distance; otherwise, it returns -1.
* Call `getDistance` to find the distance `d1` from `node1` to `i`.
* If `i` is reachable from `node1` (`d1 != -1`), call `getDistance` again to find the distance `d2` from `node2` to `i`.
* If `i` is reachable from both (`d2 != -1`), calculate `maxDist = Math.max(d1, d2)`.
* If `maxDist` is less than `min_max_dist`, update `min_max_dist` to `maxDist` and `result_node` to `i`.
* After checking all nodes, return `result_node`.

## Two Separate Traversals
A much more efficient approach is to pre-calculate the distances from `node1` and `node2` to all other nodes in the graph. We can do this in just two separate traversals. Once we have these distances, we can iterate through all the nodes once to find the one that satisfies the condition.
**Time:** O(n) - We perform two traversals, each taking at most O(n) time. The final loop to find the result node also takes O(n) time. Thus, the total time complexity is linear with respect to the number of nodes. · **Space:** O(n) - We use two arrays, `dist1` and `dist2`, each of size `n`, to store the distances from the starting nodes. This results in linear space complexity.
**Pros:** Optimal time complexity, making it efficient for large graphs.; The logic is clean and directly solves the problem without redundant work.
**Cons:** Requires O(n) extra space for the distance arrays, which might be a concern for extremely memory-constrained environments.
### Explanation
This method avoids the O(n^2) complexity by computing all required distances upfront.
1.  First, we create a distance array, `dist1`, and populate it by traversing the graph starting from `node1`. Since each node has at most one outgoing edge, this traversal is a simple walk along a path. We store the distance from `node1` to every reachable node `i` in `dist1[i]`. The traversal automatically stops at dead ends or already visited nodes, correctly handling paths and cycles.
2.  Second, we do the same for `node2`, creating and populating a `dist2` array.
3.  Finally, we iterate through all nodes `i` from `0` to `n-1`. For each node, we check if it's reachable from both starting nodes (by checking if `dist1[i]` and `dist2[i]` are not -1). If so, we calculate `max(dist1[i], dist2[i])` and compare it with the minimum maximum distance found so far. We update our answer if we find a better meeting node. Because we iterate through the nodes in increasing order of their indices, the first node we find for a given minimum distance will automatically be the one with the smallest index, satisfying the tie-breaking rule.

```java
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];
        Arrays.fill(dist1, -1);
        Arrays.fill(dist2, -1);

        // Calculate distances from node1
        calculateDistances(node1, edges, dist1);
        // Calculate distances from node2
        calculateDistances(node2, edges, dist2);

        int minMaxDist = Integer.MAX_VALUE;
        int resultNode = -1;

        for (int i = 0; i < n; i++) {
            if (dist1[i] != -1 && dist2[i] != -1) {
                int maxDist = Math.max(dist1[i], dist2[i]);
                if (maxDist < minMaxDist) {
                    minMaxDist = maxDist;
                    resultNode = i;
                }
            }
        }

        return resultNode;
    }

    private void calculateDistances(int startNode, int[] edges, int[] dist) {
        int currNode = startNode;
        int d = 0;
        while (currNode != -1 && dist[currNode] == -1) {
            dist[currNode] = d++;
            currNode = edges[currNode];
        }
    }
}
```
### Algorithm
* Create a helper function `calculateDistances(startNode, edges, dist)` that populates a given distance array.
*   Inside the helper, start a traversal from `startNode`. Since each node has at most one outgoing edge, this is a simple walk.
*   Keep track of the current distance `d`. As you visit each `currNode`, set `dist[currNode] = d` and move to the next node `edges[currNode]`.
*   Stop the traversal if you reach a dead end (`-1`) or a node that has already been visited (to handle cycles).
* Create two distance arrays, `dist1` and `dist2`, of size `n`, initialized with -1.
* Call `calculateDistances(node1, edges, dist1)` to fill `dist1` with distances from `node1`.
* Call `calculateDistances(node2, edges, dist2)` to fill `dist2` with distances from `node2`.
* Initialize `min_max_dist = Integer.MAX_VALUE` and `result_node = -1`.
* Iterate through all nodes `i` from `0` to `n-1`.
*   If `dist1[i]` and `dist2[i]` are not -1 (meaning `i` is reachable from both), calculate `maxDist = Math.max(dist1[i], dist2[i])`.
*   If `maxDist < min_max_dist`, update `min_max_dist = maxDist` and `result_node = i`.
* Return `result_node`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int ClosestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.Length;
        List < int > [] g = new List < int > [n];
        for (int i = 0; i < n; ++i) {
            g[i] = new List < int > ();
            if (edges[i] != -1) {
                g[i].Add(edges[i]);
            }
        }
        int inf = 1 << 30;
        int[] f(int i) {
            int[] dist = new int[n];
            Array.Fill(dist, inf);
            dist[i] = 0;
            Queue < int > q = new Queue < int > ();
            q.Enqueue(i);
            while (q.Count > 0) {
                i = q.Dequeue();
                foreach(int j in g[i]) {
                    if (dist[j] == inf) {
                        dist[j] = dist[i] + 1;
                        q.Enqueue(j);
                    }
                }
            }
            return dist;
        }
        int[] d1 = f(node1);
        int[] d2 = f(node2);
        int ans = -1, d = inf;
        for (int i = 0; i < n; ++i) {
            int t = Math.Max(d1[i], d2[i]);
            if (t < d) {
                d = t;
                ans = i;
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
private
  int n;
private
  List<Integer>[] g;
public
  int closestMeetingNode(int[] edges, int node1, int node2) {
    n = edges.length;
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int i = 0; i < n; ++i) {
      if (edges[i] != -1) {
        g[i].add(edges[i]);
      }
    }
    int[] d1 = dijkstra(node1);
    int[] d2 = dijkstra(node2);
    int d = 1 << 30;
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      int t = Math.max(d1[i], d2[i]);
      if (t < d) {
        d = t;
        ans = i;
      }
    }
    return ans;
  }
private
  int[] dijkstra(int i) {
    int[] dist = new int[n];
    Arrays.fill(dist, 1 << 30);
    dist[i] = 0;
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] - b[0]);
    q.offer(new int[]{0, i});
    while (!q.isEmpty()) {
      var p = q.poll();
      i = p[1];
      for (int j : g[i]) {
        if (dist[j] > dist[i] + 1) {
          dist[j] = dist[i] + 1;
          q.offer(new int[]{dist[j], j});
        }
      }
    }
    return dist;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int closestMeetingNode(vector<int> &edges, int node1, int node2) {
    int n = edges.size();
    vector<vector<int>> g(n);
    for (int i = 0; i < n; ++i) {
      if (edges[i] != -1) {
        g[i].push_back(edges[i]);
      }
    }
    const int inf = 1 << 30;
    using pii = pair<int, int>;
    auto dijkstra = [&](int i) {
      vector<int> dist(n, inf);
      dist[i] = 0;
      priority_queue<pii, vector<pii>, greater<pii>> q;
      q.emplace(0, i);
      while (!q.empty()) {
        auto p = q.top();
        q.pop();
        i = p.second;
        for (int j : g[i]) {
          if (dist[j] > dist[i] + 1) {
            dist[j] = dist[i] + 1;
            q.emplace(dist[j], j);
          }
        }
      }
      return dist;
    };
    vector<int> d1 = dijkstra(node1);
    vector<int> d2 = dijkstra(node2);
    int ans = -1, d = inf;
    for (int i = 0; i < n; ++i) {
      int t = max(d1[i], d2[i]);
      if (t < d) {
        d = t;
        ans = i;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int: def dijkstra(i): dist = [inf] * n dist[i] = 0 q = [(0, i)] while q: i = heappop(q)[1] for j in g[i]: if dist[j] > dist[i] + 1: dist[j] = dist[i] + 1 heappush(q, (dist[j], j)) return dist g = defaultdict(list) for i, j in enumerate(edges): if j != - 1: g[i]. append(j) n = len(edges) d1 = dijkstra(node1) d2 = dijkstra(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

```