2359. Find Closest Node to Given Two Nodes - Explanation

Description

The array edges describes a directed graph with n = edges.length nodes labeled 0 through n - 1. A value edges[i] = j gives an edge from i to j, while -1 means node i has no outgoing edge. Cycles are allowed.

Find a node reachable from both node1 and node2 that minimizes the larger of the two shortest-path distances to it. A distance is the number of edges traveled; a node is distance zero from itself.

Return the chosen node's label. If several nodes achieve the same minimum, return the smallest label. If no node is reachable from both starting nodes, return -1.

Example 1:

Find Closest Node to Given Two Nodes, example 1: illustration of the example

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

Output: 0

Explanation: Nodes 0 and 2 both have maximum distance 2 from the two starting nodes. Nodes 1 and 3 have maximum distance 3. The tie between 0 and 2 is resolved by choosing the smaller label, 0.

Example 2:

Find Closest Node to Given Two Nodes, example 2: illustration of the example

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

Output: -1

Explanation: Node 0 can reach only nodes 0 and 1, while node 2 can reach only nodes 2 and 3. There is no common reachable node.

Example 3:

Find Closest Node to Given Two Nodes, example 3: illustration of the example

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

Output: 1

Explanation: Both starting nodes are node 1. Its distance from itself is 0, which is the smallest possible maximum distance.

Constraints:

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

Topics

Graph Depth-First Search

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Representation - Understanding adjacency lists and how to represent directed graphs from edge arrays
Breadth-First Search (BFS) - Computing shortest distances in unweighted graphs using queue-based traversal
Depth-First Search (DFS) - Traversing graph paths iteratively or recursively while tracking visited nodes

1. Breadth First Search

Intuition

We want a node reachable from both node1 and node2 that minimizes the maximum of the two distances. First, we compute distances from node1 to all reachable nodes, then do the same from node2. For each node reachable from both, the "cost" is the larger of the two distances. We pick the node with the smallest such cost, breaking ties by choosing the smaller index.

Algorithm

Build an adjacency list from the edges array.
Run BFS from node1 to compute distances to all reachable nodes, storing them in node1Dist.
Run BFS from node2 to compute distances, storing them in node2Dist.
Iterate through all nodes. For each node reachable from both sources:
- Compute dist = max(node1Dist[i], node2Dist[i]).
- If this is smaller than the best seen so far, update the result.
Return the best node index, or -1 if none exists.

class Solution:
    def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:
        adj = defaultdict(list)
        for i, nei in enumerate(edges):
            adj[i].append(nei)

        def bfs(src, distMap):
            q = deque([(src, 0)])
            distMap[src] = 0
            while q:
                node, dist = q.popleft()
                for nei in adj[node]:
                    if nei not in distMap:
                        q.append((nei, dist + 1))
                        distMap[nei] = dist + 1

        node1Dist, node2Dist = {}, {}
        bfs(node1, node1Dist)
        bfs(node2, node2Dist)

        res, resDist = -1, float("inf")
        for i in range(len(edges)):
            if i in node1Dist and i in node2Dist:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i

        return res

public class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (edges[i] != -1) adj[i].add(edges[i]);
        }

        int[] node1Dist = bfs(node1, n, adj);
        int[] node2Dist = bfs(node2, n, adj);

        int res = -1, resDist = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (node1Dist[i] != -1 && node2Dist[i] != -1) {
                int dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }

    private int[] bfs(int src, int n, List<Integer>[] adj) {
        int[] distMap = new int[n];
        Arrays.fill(distMap, -1);
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{src, 0});
        distMap[src] = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int node = cur[0], dist = cur[1];

            for (int nei : adj[node]) {
                if (distMap[nei] == -1) {
                    q.offer(new int[]{nei, dist + 1});
                    distMap[nei] = dist + 1;
                }
            }
        }
        return distMap;
    }
}

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n = edges.size();
        vector<vector<int>> adj(n);
        for (int i = 0; i < n; i++) {
            if (edges[i] != -1) adj[i].push_back(edges[i]);
        }

        vector<int> node1Dist = bfs(node1, n, adj);
        vector<int> node2Dist = bfs(node2, n, adj);

        int res = -1, resDist = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (node1Dist[i] != -1 && node2Dist[i] != -1) {
                int dist = max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }

private:
    vector<int> bfs(int src, int n, vector<vector<int>>& adj) {
        vector<int> distMap(n, -1);
        queue<pair<int, int>> q;
        q.push({src, 0});
        distMap[src] = 0;

        while (!q.empty()) {
            auto [node, dist] = q.front();
            q.pop();

            for (int nei : adj[node]) {
                if (distMap[nei] == -1) {
                    q.push({nei, dist + 1});
                    distMap[nei] = dist + 1;
                }
            }
        }
        return distMap;
    }
};

class Solution {
    /**
     * @param {number[]} edges
     * @param {number} node1
     * @param {number} node2
     * @return {number}
     */
    closestMeetingNode(edges, node1, node2) {
        const n = edges.length;
        const adj = Array.from({ length: n }, () => []);
        for (let i = 0; i < n; i++) {
            if (edges[i] !== -1) adj[i].push(edges[i]);
        }

        const bfs = (src) => {
            const distMap = Array(n).fill(-1);
            const q = new Queue([[src, 0]]);
            distMap[src] = 0;

            while (!q.isEmpty()) {
                const [node, dist] = q.pop();
                for (const nei of adj[node]) {
                    if (distMap[nei] === -1) {
                        q.push([nei, dist + 1]);
                        distMap[nei] = dist + 1;
                    }
                }
            }
            return distMap;
        };

        const node1Dist = bfs(node1);
        const node2Dist = bfs(node2);

        let res = -1,
            resDist = Infinity;
        for (let i = 0; i < n; i++) {
            if (node1Dist[i] !== -1 && node2Dist[i] !== -1) {
                let dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }
}

func closestMeetingNode(edges []int, node1 int, node2 int) int {
    n := len(edges)
    adj := make([][]int, n)
    for i := 0; i < n; i++ {
        adj[i] = []int{}
        if edges[i] != -1 {
            adj[i] = append(adj[i], edges[i])
        }
    }

    bfs := func(src int) []int {
        distMap := make([]int, n)
        for i := range distMap {
            distMap[i] = -1
        }
        q := [][]int{{src, 0}}
        distMap[src] = 0

        for len(q) > 0 {
            node, dist := q[0][0], q[0][1]
            q = q[1:]
            for _, nei := range adj[node] {
                if distMap[nei] == -1 {
                    q = append(q, []int{nei, dist + 1})
                    distMap[nei] = dist + 1
                }
            }
        }
        return distMap
    }

    node1Dist := bfs(node1)
    node2Dist := bfs(node2)

    res, resDist := -1, math.MaxInt32
    for i := 0; i < n; i++ {
        if node1Dist[i] != -1 && node2Dist[i] != -1 {
            dist := max(node1Dist[i], node2Dist[i])
            if dist < resDist {
                resDist = dist
                res = i
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val n = edges.size
        val adj = Array(n) { mutableListOf<Int>() }
        for (i in 0 until n) {
            if (edges[i] != -1) adj[i].add(edges[i])
        }

        fun bfs(src: Int): IntArray {
            val distMap = IntArray(n) { -1 }
            val q: ArrayDeque<Pair<Int, Int>> = ArrayDeque()
            q.add(Pair(src, 0))
            distMap[src] = 0

            while (q.isNotEmpty()) {
                val (node, dist) = q.removeFirst()
                for (nei in adj[node]) {
                    if (distMap[nei] == -1) {
                        q.add(Pair(nei, dist + 1))
                        distMap[nei] = dist + 1
                    }
                }
            }
            return distMap
        }

        val node1Dist = bfs(node1)
        val node2Dist = bfs(node2)

        var res = -1
        var resDist = Int.MAX_VALUE
        for (i in 0 until n) {
            if (node1Dist[i] != -1 && node2Dist[i] != -1) {
                val dist = maxOf(node1Dist[i], node2Dist[i])
                if (dist < resDist) {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

class Solution {
    func closestMeetingNode(_ edges: [Int], _ node1: Int, _ node2: Int) -> Int {
        let n = edges.count
        var adj = [[Int]](repeating: [], count: n)
        for i in 0..<n {
            if edges[i] != -1 {
                adj[i].append(edges[i])
            }
        }

        func bfs(_ src: Int) -> [Int] {
            var distMap = [Int](repeating: -1, count: n)
            var q = [(src, 0)]
            distMap[src] = 0

            while !q.isEmpty {
                let (node, dist) = q.removeFirst()
                for nei in adj[node] {
                    if distMap[nei] == -1 {
                        q.append((nei, dist + 1))
                        distMap[nei] = dist + 1
                    }
                }
            }
            return distMap
        }

        let node1Dist = bfs(node1)
        let node2Dist = bfs(node2)

        var res = -1
        var resDist = Int.max
        for i in 0..<n {
            if node1Dist[i] != -1 && node2Dist[i] != -1 {
                let dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

impl Solution {
    pub fn closest_meeting_node(edges: Vec<i32>, node1: i32, node2: i32) -> i32 {
        let n = edges.len();
        let mut adj = vec![vec![]; n];
        for i in 0..n {
            if edges[i] != -1 {
                adj[i].push(edges[i] as usize);
            }
        }

        let bfs = |src: usize| -> Vec<i32> {
            let mut dist = vec![-1i32; n];
            let mut q = VecDeque::new();
            q.push_back((src, 0i32));
            dist[src] = 0;
            while let Some((node, d)) = q.pop_front() {
                for &nei in &adj[node] {
                    if dist[nei] == -1 {
                        q.push_back((nei, d + 1));
                        dist[nei] = d + 1;
                    }
                }
            }
            dist
        };

        let node1_dist = bfs(node1 as usize);
        let node2_dist = bfs(node2 as usize);

        let mut res = -1i32;
        let mut res_dist = i32::MAX;
        for i in 0..n {
            if node1_dist[i] != -1 && node2_dist[i] != -1 {
                let dist = node1_dist[i].max(node2_dist[i]);
                if dist < res_dist {
                    res_dist = dist;
                    res = i as i32;
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Breadth First Search (Optimal)

Intuition

Since each node has at most one outgoing edge, we do not need a full adjacency list. We can traverse directly using the edges array. The BFS logic remains the same, but we simplify by following edges[node] directly instead of iterating through neighbors.

Algorithm

Run BFS from node1: follow edges[node] until we hit -1 or revisit a node, recording distances in node1Dist.
Run BFS from node2 the same way, storing results in node2Dist.
Scan all nodes. For each one reachable from both sources, track the minimum of max(node1Dist[i], node2Dist[i]).
Return the node with the smallest maximum distance, or -1 if unreachable.

class Solution:
    def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:
        n = len(edges)

        def bfs(src):
            dist = [-1] * n
            q = deque([src])
            dist[src] = 0

            while q:
                node = q.popleft()
                nei = edges[node]
                if nei == -1 or dist[nei] >= 0:
                    continue
                q.append(nei)
                dist[nei] = dist[node] + 1
            return dist

        node1Dist, node2Dist = bfs(node1), bfs(node2)

        res, resDist = -1, float("inf")
        for i in range(n):
            if node1Dist[i] != -1 and node2Dist[i] != -1:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i

        return res

public class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] node1Dist = bfs(node1, edges, n);
        int[] node2Dist = bfs(node2, edges, n);

        int res = -1, resDist = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (node1Dist[i] != -1 && node2Dist[i] != -1) {
                int dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }

        return res;
    }

    private int[] bfs(int src, int[] edges, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        q.offer(src);
        dist[src] = 0;

        while (!q.isEmpty()) {
            int node = q.poll();
            int nei = edges[node];
            if (nei == -1 || dist[nei] != -1) {
                continue;
            }

            q.offer(nei);
            dist[nei] = dist[node] + 1;
        }
        return dist;
    }
}

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n = edges.size();
        vector<int> node1Dist = bfs(node1, edges, n);
        vector<int> node2Dist = bfs(node2, edges, n);

        int res = -1, resDist = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (node1Dist[i] != -1 && node2Dist[i] != -1) {
                int dist = max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }

private:
    vector<int> bfs(int src, vector<int>& edges, int n) {
        vector<int> dist(n, -1);
        queue<int> q;
        q.push(src);
        dist[src] = 0;

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            int nei = edges[node];
            if (nei == -1 || dist[nei] != -1) {
                continue;
            }

            q.push(nei);
            dist[nei] = dist[node] + 1;
        }
        return dist;
    }
};

class Solution {
    /**
     * @param {number[]} edges
     * @param {number} node1
     * @param {number} node2
     * @return {number}
     */
    closestMeetingNode(edges, node1, node2) {
        const n = edges.length;

        const bfs = (src) => {
            const dist = Array(n).fill(-1);
            const q = new Queue([src]);
            dist[src] = 0;

            while (!q.isEmpty()) {
                const node = q.pop();
                const nei = edges[node];
                if (nei === -1 || dist[nei] !== -1) {
                    continue;
                }

                q.push(nei);
                dist[nei] = dist[node] + 1;
            }
            return dist;
        };

        const node1Dist = bfs(node1);
        const node2Dist = bfs(node2);

        let res = -1,
            resDist = Infinity;
        for (let i = 0; i < n; i++) {
            if (node1Dist[i] !== -1 && node2Dist[i] !== -1) {
                let dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }
}

func closestMeetingNode(edges []int, node1 int, node2 int) int {
    n := len(edges)

    bfs := func(src int) []int {
        dist := make([]int, n)
        for i := range dist {
            dist[i] = -1
        }
        q := []int{src}
        dist[src] = 0

        for len(q) > 0 {
            node := q[0]
            q = q[1:]
            nei := edges[node]
            if nei == -1 || dist[nei] != -1 {
                continue
            }
            q = append(q, nei)
            dist[nei] = dist[node] + 1
        }
        return dist
    }

    node1Dist := bfs(node1)
    node2Dist := bfs(node2)

    res, resDist := -1, math.MaxInt32
    for i := 0; i < n; i++ {
        if node1Dist[i] != -1 && node2Dist[i] != -1 {
            dist := max(node1Dist[i], node2Dist[i])
            if dist < resDist {
                resDist = dist
                res = i
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val n = edges.size

        fun bfs(src: Int): IntArray {
            val dist = IntArray(n) { -1 }
            val q: ArrayDeque<Int> = ArrayDeque()
            q.add(src)
            dist[src] = 0

            while (q.isNotEmpty()) {
                val node = q.removeFirst()
                val nei = edges[node]
                if (nei == -1 || dist[nei] != -1) {
                    continue
                }
                q.add(nei)
                dist[nei] = dist[node] + 1
            }
            return dist
        }

        val node1Dist = bfs(node1)
        val node2Dist = bfs(node2)

        var res = -1
        var resDist = Int.MAX_VALUE
        for (i in 0 until n) {
            if (node1Dist[i] != -1 && node2Dist[i] != -1) {
                val dist = maxOf(node1Dist[i], node2Dist[i])
                if (dist < resDist) {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

class Solution {
    func closestMeetingNode(_ edges: [Int], _ node1: Int, _ node2: Int) -> Int {
        let n = edges.count

        func bfs(_ src: Int) -> [Int] {
            var dist = [Int](repeating: -1, count: n)
            var q = [src]
            dist[src] = 0

            while !q.isEmpty {
                let node = q.removeFirst()
                let nei = edges[node]
                if nei == -1 || dist[nei] != -1 {
                    continue
                }
                q.append(nei)
                dist[nei] = dist[node] + 1
            }
            return dist
        }

        let node1Dist = bfs(node1)
        let node2Dist = bfs(node2)

        var res = -1
        var resDist = Int.max
        for i in 0..<n {
            if node1Dist[i] != -1 && node2Dist[i] != -1 {
                let dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

impl Solution {
    pub fn closest_meeting_node(edges: Vec<i32>, node1: i32, node2: i32) -> i32 {
        let n = edges.len();

        let bfs = |src: usize| -> Vec<i32> {
            let mut dist = vec![-1i32; n];
            let mut q = VecDeque::new();
            q.push_back(src);
            dist[src] = 0;
            while let Some(node) = q.pop_front() {
                let nei = edges[node];
                if nei == -1 || dist[nei as usize] != -1 {
                    continue;
                }
                q.push_back(nei as usize);
                dist[nei as usize] = dist[node] + 1;
            }
            dist
        };

        let node1_dist = bfs(node1 as usize);
        let node2_dist = bfs(node2 as usize);

        let mut res = -1i32;
        let mut res_dist = i32::MAX;
        for i in 0..n {
            if node1_dist[i] != -1 && node2_dist[i] != -1 {
                let dist = node1_dist[i].max(node2_dist[i]);
                if dist < res_dist {
                    res_dist = dist;
                    res = i as i32;
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Depth First Search

Intuition

DFS achieves the same goal as BFS here. Starting from each source node, we recursively follow edges and record distances. The graph structure (each node has at most one outgoing edge) means DFS naturally follows the single path from each source without branching.

Algorithm

Initialize distance arrays node1Dist and node2Dist with -1 (unreachable).
Set node1Dist[node1] = 0 and node2Dist[node2] = 0.
Run DFS from node1: for each unvisited neighbor, set its distance and recurse.
Run DFS from node2 similarly.
Find the node with the minimum value of max(node1Dist[i], node2Dist[i]) among nodes reachable from both.
Return that node, or -1 if none.

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)

        def dfs(node, dist):
            nei = edges[node]
            if nei != -1 and dist[nei] == -1:
                dist[nei] = dist[node] + 1
                dfs(nei, dist)

        node1Dist = [-1] * n
        node2Dist = [-1] * n
        node1Dist[node1] = node2Dist[node2] = 0

        dfs(node1, node1Dist)
        dfs(node2, node2Dist)

        res, resDist = -1, float("inf")
        for i in range(n):
            if min(node1Dist[i], node2Dist[i]) != -1:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i

        return res

public class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] node1Dist = new int[n];
        int[] node2Dist = new int[n];
        Arrays.fill(node1Dist, -1);
        Arrays.fill(node2Dist, -1);
        node1Dist[node1] = 0;
        node2Dist[node2] = 0;

        dfs(node1, edges, node1Dist);
        dfs(node2, edges, node2Dist);

        int res = -1, resDist = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (Math.min(node1Dist[i], node2Dist[i]) != -1) {
                int dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }

    private void dfs(int node, int[] edges, int[] dist) {
        int nei = edges[node];
        if (nei != -1 && dist[nei] == -1) {
            dist[nei] = dist[node] + 1;
            dfs(nei, edges, dist);
        }
    }
}

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n = edges.size();
        vector<int> node1Dist(n, -1), node2Dist(n, -1);
        node1Dist[node1] = node2Dist[node2] = 0;

        dfs(node1, edges, node1Dist);
        dfs(node2, edges, node2Dist);

        int res = -1, resDist = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (min(node1Dist[i], node2Dist[i]) != -1) {
                int dist = max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }

private:
    void dfs(int node, vector<int>& edges, vector<int>& dist) {
        int nei = edges[node];
        if (nei != -1 && dist[nei] == -1) {
            dist[nei] = dist[node] + 1;
            dfs(nei, edges, dist);
        }
    }
};

class Solution {
    /**
     * @param {number[]} edges
     * @param {number} node1
     * @param {number} node2
     * @return {number}
     */
    closestMeetingNode(edges, node1, node2) {
        const n = edges.length;

        const dfs = (node, dist) => {
            const nei = edges[node];
            if (nei !== -1 && dist[nei] === -1) {
                dist[nei] = dist[node] + 1;
                dfs(nei, dist);
            }
        };

        const node1Dist = Array(n).fill(-1);
        const node2Dist = Array(n).fill(-1);
        node1Dist[node1] = 0;
        node2Dist[node2] = 0;

        dfs(node1, node1Dist);
        dfs(node2, node2Dist);

        let res = -1,
            resDist = Infinity;
        for (let i = 0; i < n; i++) {
            if (Math.min(node1Dist[i], node2Dist[i]) !== -1) {
                const dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }
}

func closestMeetingNode(edges []int, node1 int, node2 int) int {
    n := len(edges)

    var dfs func(node int, dist []int)
    dfs = func(node int, dist []int) {
        nei := edges[node]
        if nei != -1 && dist[nei] == -1 {
            dist[nei] = dist[node] + 1
            dfs(nei, dist)
        }
    }

    node1Dist := make([]int, n)
    node2Dist := make([]int, n)
    for i := range node1Dist {
        node1Dist[i] = -1
        node2Dist[i] = -1
    }
    node1Dist[node1] = 0
    node2Dist[node2] = 0

    dfs(node1, node1Dist)
    dfs(node2, node2Dist)

    res, resDist := -1, math.MaxInt32
    for i := 0; i < n; i++ {
        if min(node1Dist[i], node2Dist[i]) != -1 {
            dist := max(node1Dist[i], node2Dist[i])
            if dist < resDist {
                resDist = dist
                res = i
            }
        }
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val n = edges.size

        fun dfs(node: Int, dist: IntArray) {
            val nei = edges[node]
            if (nei != -1 && dist[nei] == -1) {
                dist[nei] = dist[node] + 1
                dfs(nei, dist)
            }
        }

        val node1Dist = IntArray(n) { -1 }
        val node2Dist = IntArray(n) { -1 }
        node1Dist[node1] = 0
        node2Dist[node2] = 0

        dfs(node1, node1Dist)
        dfs(node2, node2Dist)

        var res = -1
        var resDist = Int.MAX_VALUE
        for (i in 0 until n) {
            if (minOf(node1Dist[i], node2Dist[i]) != -1) {
                val dist = maxOf(node1Dist[i], node2Dist[i])
                if (dist < resDist) {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

class Solution {
    func closestMeetingNode(_ edges: [Int], _ node1: Int, _ node2: Int) -> Int {
        let n = edges.count

        func dfs(_ node: Int, _ dist: inout [Int]) {
            let nei = edges[node]
            if nei != -1 && dist[nei] == -1 {
                dist[nei] = dist[node] + 1
                dfs(nei, &dist)
            }
        }

        var node1Dist = [Int](repeating: -1, count: n)
        var node2Dist = [Int](repeating: -1, count: n)
        node1Dist[node1] = 0
        node2Dist[node2] = 0

        dfs(node1, &node1Dist)
        dfs(node2, &node2Dist)

        var res = -1
        var resDist = Int.max
        for i in 0..<n {
            if min(node1Dist[i], node2Dist[i]) != -1 {
                let dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

impl Solution {
    pub fn closest_meeting_node(edges: Vec<i32>, node1: i32, node2: i32) -> i32 {
        let n = edges.len();

        fn dfs(node: usize, edges: &[i32], dist: &mut Vec<i32>) {
            let nei = edges[node];
            if nei != -1 && dist[nei as usize] == -1 {
                dist[nei as usize] = dist[node] + 1;
                dfs(nei as usize, edges, dist);
            }
        }

        let mut node1_dist = vec![-1i32; n];
        let mut node2_dist = vec![-1i32; n];
        node1_dist[node1 as usize] = 0;
        node2_dist[node2 as usize] = 0;

        dfs(node1 as usize, &edges, &mut node1_dist);
        dfs(node2 as usize, &edges, &mut node2_dist);

        let mut res = -1i32;
        let mut res_dist = i32::MAX;
        for i in 0..n {
            if node1_dist[i].min(node2_dist[i]) != -1 {
                let dist = node1_dist[i].max(node2_dist[i]);
                if dist < res_dist {
                    res_dist = dist;
                    res = i as i32;
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Iterative Depth First Search

Intuition

Since each node has exactly one outgoing edge, we can replace recursion with a simple while loop. Starting from each source, we follow edges iteratively until we reach -1 or a visited node. This avoids recursion overhead while computing the same distances.

Algorithm

For each source node, initialize its distance to 0.
Iteratively follow edges[node] while the neighbor exists and is unvisited:
- Set the neighbor's distance to current distance + 1.
- Move to the neighbor.
Repeat for both node1 and node2.
Find the node minimizing max(node1Dist[i], node2Dist[i]) among doubly-reachable nodes.
Return the result.

class Solution:
    def closestMeetingNode(self, edges: list[int], node1: int, node2: int) -> int:
        n = len(edges)

        def dfs(node):
            dist = [-1] * n
            dist[node] = 0
            while edges[node] != -1 and dist[edges[node]] == -1:
                nei = edges[node]
                dist[nei] = dist[node] + 1
                node = nei
            return dist

        node1Dist, node2Dist = dfs(node1), dfs(node2)
        res, resDist = -1, float("inf")
        for i in range(n):
            if min(node1Dist[i], node2Dist[i]) != -1:
                dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist:
                    resDist, res = dist, i
        return res

public class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] node1Dist = dfs(node1, edges, n);
        int[] node2Dist = dfs(node2, edges, n);

        int res = -1, resDist = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (Math.min(node1Dist[i], node2Dist[i]) != -1) {
                int dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }

    private int[] dfs(int node, int[] edges, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[node] = 0;
        while (edges[node] != -1 && dist[edges[node]] == -1) {
            int nei = edges[node];
            dist[nei] = dist[node] + 1;
            node = nei;
        }
        return dist;
    }
}

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n = edges.size();
        vector<int> node1Dist = dfs(node1, edges, n);
        vector<int> node2Dist = dfs(node2, edges, n);

        int res = -1, resDist = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (min(node1Dist[i], node2Dist[i]) != -1) {
                int dist = max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }

private:
    vector<int> dfs(int node, vector<int>& edges, int n) {
        vector<int> dist(n, -1);
        dist[node] = 0;
        while (edges[node] != -1 && dist[edges[node]] == -1) {
            int nei = edges[node];
            dist[nei] = dist[node] + 1;
            node = nei;
        }
        return dist;
    }
};

class Solution {
    /**
     * @param {number[]} edges
     * @param {number} node1
     * @param {number} node2
     * @return {number}
     */
    closestMeetingNode(edges, node1, node2) {
        const n = edges.length;

        const dfs = (node) => {
            const dist = Array(n).fill(-1);
            dist[node] = 0;
            while (edges[node] !== -1 && dist[edges[node]] === -1) {
                const nei = edges[node];
                dist[nei] = dist[node] + 1;
                node = nei;
            }
            return dist;
        };

        const node1Dist = dfs(node1);
        const node2Dist = dfs(node2);

        let res = -1,
            resDist = Infinity;
        for (let i = 0; i < n; i++) {
            if (Math.min(node1Dist[i], node2Dist[i]) !== -1) {
                const dist = Math.max(node1Dist[i], node2Dist[i]);
                if (dist < resDist) {
                    resDist = dist;
                    res = i;
                }
            }
        }
        return res;
    }
}

func closestMeetingNode(edges []int, node1 int, node2 int) int {
    n := len(edges)

    dfs := func(node int) []int {
        dist := make([]int, n)
        for i := range dist {
            dist[i] = -1
        }
        dist[node] = 0
        for edges[node] != -1 && dist[edges[node]] == -1 {
            nei := edges[node]
            dist[nei] = dist[node] + 1
            node = nei
        }
        return dist
    }

    node1Dist := dfs(node1)
    node2Dist := dfs(node2)

    res, resDist := -1, math.MaxInt32
    for i := 0; i < n; i++ {
        if min(node1Dist[i], node2Dist[i]) != -1 {
            dist := max(node1Dist[i], node2Dist[i])
            if dist < resDist {
                resDist = dist
                res = i
            }
        }
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val n = edges.size

        fun dfs(startNode: Int): IntArray {
            val dist = IntArray(n) { -1 }
            var node = startNode
            dist[node] = 0
            while (edges[node] != -1 && dist[edges[node]] == -1) {
                val nei = edges[node]
                dist[nei] = dist[node] + 1
                node = nei
            }
            return dist
        }

        val node1Dist = dfs(node1)
        val node2Dist = dfs(node2)

        var res = -1
        var resDist = Int.MAX_VALUE
        for (i in 0 until n) {
            if (minOf(node1Dist[i], node2Dist[i]) != -1) {
                val dist = maxOf(node1Dist[i], node2Dist[i])
                if (dist < resDist) {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

class Solution {
    func closestMeetingNode(_ edges: [Int], _ node1: Int, _ node2: Int) -> Int {
        let n = edges.count

        func dfs(_ startNode: Int) -> [Int] {
            var dist = [Int](repeating: -1, count: n)
            var node = startNode
            dist[node] = 0
            while edges[node] != -1 && dist[edges[node]] == -1 {
                let nei = edges[node]
                dist[nei] = dist[node] + 1
                node = nei
            }
            return dist
        }

        let node1Dist = dfs(node1)
        let node2Dist = dfs(node2)

        var res = -1
        var resDist = Int.max
        for i in 0..<n {
            if min(node1Dist[i], node2Dist[i]) != -1 {
                let dist = max(node1Dist[i], node2Dist[i])
                if dist < resDist {
                    resDist = dist
                    res = i
                }
            }
        }
        return res
    }
}

impl Solution {
    pub fn closest_meeting_node(edges: Vec<i32>, node1: i32, node2: i32) -> i32 {
        let n = edges.len();

        let dfs = |start: usize| -> Vec<i32> {
            let mut dist = vec![-1i32; n];
            let mut node = start;
            dist[node] = 0;
            while edges[node] != -1 && dist[edges[node] as usize] == -1 {
                let nei = edges[node] as usize;
                dist[nei] = dist[node] + 1;
                node = nei;
            }
            dist
        };

        let node1_dist = dfs(node1 as usize);
        let node2_dist = dfs(node2 as usize);

        let mut res = -1i32;
        let mut res_dist = i32::MAX;
        for i in 0..n {
            if node1_dist[i].min(node2_dist[i]) != -1 {
                let dist = node1_dist[i].max(node2_dist[i]);
                if dist < res_dist {
                    res_dist = dist;
                    res = i as i32;
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Using Sum Instead of Maximum Distance

The problem asks for the node that minimizes the maximum of the two distances, not the sum. Using node1Dist[i] + node2Dist[i] instead of max(node1Dist[i], node2Dist[i]) produces incorrect results.

Not Handling Cycles Properly

The graph can contain cycles, so distance computation must mark visited nodes to avoid infinite loops. Always check if a node has already been assigned a distance before processing it.

Forgetting to Return the Smallest Index on Ties

When multiple nodes have the same minimum maximum distance, the problem requires returning the smallest index. Iterating from index 0 and using strict less-than comparison ensures the first valid node is selected.