Find Closest Node to Given Two Nodes

medium graph dfs bfs

Problem

Given a directed graph where each node has at most one outgoing edge (encoded as edges[i] = -1 or the destination), and two start nodes, return the node reachable from both that minimizes the larger of the two distances (ties broken by smallest index). Return -1 if no such node exists.

Inputedges = [2,2,3,-1], node1 = 0, node2 = 1

Output2

From 0 → 2 (dist 1); from 1 → 2 (dist 1). max(1,1)=1, smallest.

edges (comma; -1 = none)

node1

node2

def closest_meeting_node(edges, node1, node2):
    def dist(start):
        d = [-1] * len(edges)
        cur, step = start, 0
        while cur != -1 and d[cur] == -1:
            d[cur] = step
            step += 1
            cur = edges[cur]
        return d
    d1, d2 = dist(node1), dist(node2)
    best, ans = float("inf"), -1
    for i in range(len(edges)):
        if d1[i] != -1 and d2[i] != -1:
            m = max(d1[i], d2[i])
            if m < best:
                best, ans = m, i
    return ans

function closestMeetingNode(edges, node1, node2) {
  function dist(start) {
    const d = new Array(edges.length).fill(-1);
    let cur = start, step = 0;
    while (cur !== -1 && d[cur] === -1) {
      d[cur] = step++;
      cur = edges[cur];
    }
    return d;
  }
  const d1 = dist(node1), d2 = dist(node2);
  let best = Infinity, ans = -1;
  for (let i = 0; i < edges.length; i++) {
    if (d1[i] !== -1 && d2[i] !== -1) {
      const m = Math.max(d1[i], d2[i]);
      if (m < best) { best = m; ans = i; }
    }
  }
  return ans;
}

class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int[] d1 = dist(edges, node1), d2 = dist(edges, node2);
        int best = Integer.MAX_VALUE, ans = -1;
        for (int i = 0; i < edges.length; i++) {
            if (d1[i] != -1 && d2[i] != -1) {
                int m = Math.max(d1[i], d2[i]);
                if (m < best) { best = m; ans = i; }
            }
        }
        return ans;
    }
    private int[] dist(int[] edges, int start) {
        int[] d = new int[edges.length];
        Arrays.fill(d, -1);
        int cur = start, step = 0;
        while (cur != -1 && d[cur] == -1) { d[cur] = step++; cur = edges[cur]; }
        return d;
    }
}

vector<int> dist(vector<int>& edges, int start) {
    vector<int> d(edges.size(), -1);
    int cur = start, step = 0;
    while (cur != -1 && d[cur] == -1) { d[cur] = step++; cur = edges[cur]; }
    return d;
}
int closestMeetingNode(vector<int>& edges, int node1, int node2) {
    auto d1 = dist(edges, node1), d2 = dist(edges, node2);
    int best = INT_MAX, ans = -1;
    for (int i = 0; i < (int)edges.size(); i++) {
        if (d1[i] != -1 && d2[i] != -1) {
            int m = max(d1[i], d2[i]);
            if (m < best) { best = m; ans = i; }
        }
    }
    return ans;
}

Explanation

Every node has at most one outgoing edge, so starting anywhere you just follow a single path until it ends or loops. We measure how far each node is from node1 and from node2, then pick the meeting point that minimizes the larger of the two distances.

The helper dist(start) walks the chain, recording d[cur] = step for each node it reaches. It stops when it hits -1 (no outgoing edge) or revisits a node (d[cur] != -1), which prevents getting stuck in a cycle.

After computing d1 and d2, we scan every node reachable from both (neither distance is -1) and track the smallest value of max(d1[i], d2[i]). We use max because both starters have to actually arrive there, so the slower one decides the meeting time.

Example: edges=[2,2,3,-1], node1=0, node2=1. From 0 we reach node 2 at distance 1; from 1 we also reach node 2 at distance 1. max(1,1)=1 is the smallest, so the answer is 2.

Because the scan goes left to right and only updates on a strictly smaller max, ties are naturally broken toward the smallest index, and unreachable cases return -1.

Time: O(n) Space: O(n)