Find Closest Node to Given Two Nodes solution and explanation
Google
9 more videos on this problem
Find Closest Node to Given Two Nodes - Leetcode 2359 - PythonNeetCodeIO · 10:52 · 9K views
Leetcode 2359. Find Closest Node to Given Two Nodes | Weekly Contest 304. Problem 3 MediumCode with Alisha · 19:35 · 3K views
2359. Find Closest Node to Given Two Nodes || Leetcode Weekly Contest 304Bro Coders · 13:43 · 2K views
Weekly Contest 304 | 2359. Find Closest Node to Given Two NodescodingMohan · 11:25 · 1K views
Leetcode 2359 Find Closest Node to Given Two Nodes | Easy Peasy Graphs | SDE preparation sheetCoding Decoded · 7:30 · 1K views
Find Closest Node to Given Two Nodes | Leetcode 2359Techdose · 27:18 · 1K views
2359 || Find Closest Node to Given Two Nodes || Leetcode Daily ChallengeCodeFreaks · 18:44 · 468 views
2359. Find Closest Node to Given Two Nodes | LeetCodeDeep Tech · 16:06 · 394 views
Leetcode 2359 Find Closest Node to Given Two Nodes (Java) - Beats 100%TheAnalyticGuy · 9:38 · 313 views
Leetcode 2359: Find Closest Node to Given Two NodesAlgorithms Casts · 17:12 · 243 views
The 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:
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:
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.length2 <= n <= 105-1 <= edges[i] < nedges[i] != i0 <= node1, node2 < n
Approach overview
Problem Overview: You are given a directed graph where each node has at most one outgoing edge. Starting from node1 and node2, find a node reachable from both such that the maximum of the two distances is minimized. If multiple nodes satisfy this condition, return the smallest index.
Approach 1: BFS for Shortest Path (O(n) time, O(n) space)
Treat the structure as a directed graph where each node points to at most one neighbor. Run a BFS (or simple forward traversal) from node1 to compute the shortest distance to every reachable node. Repeat the process from node2. After both distance arrays are built, iterate through all nodes and compute max(dist1[i], dist2[i]) for nodes reachable from both sources. Track the node with the smallest maximum distance and smallest index in case of ties. This works because BFS guarantees the shortest path in an unweighted graph.
This approach directly applies standard graph traversal techniques and is efficient since each node is processed at most once per traversal. With only one outgoing edge per node, the traversal behaves almost like following linked lists, keeping the runtime linear.
Approach 2: DFS for Shortest Path and Avoiding Cycles (O(n) time, O(n) space)
Use Depth-First Search to explore paths starting from each source node while tracking distances. Maintain a visited set or distance array to avoid revisiting nodes, which prevents infinite loops caused by cycles. Each recursive call records the current distance before moving to the next neighbor defined by edges[i]. After computing distance arrays for both starting nodes, scan through all nodes and select the one minimizing max(dist1[i], dist2[i]).
DFS works well because every node has only one outgoing edge, so the recursion path is straightforward and cycle detection is easy. The algorithm still processes each node at most once per traversal, keeping the complexity linear.
Recommended for interviews: The BFS-style traversal is typically preferred because it explicitly models shortest paths in an unweighted graph. It is easier to reason about distances and avoids recursion overhead. Showing the DFS variant demonstrates understanding of DFS and cycle handling, but interviewers usually expect the linear shortest-distance approach.
Approach 1: Approach 1: BFS for Shortest Path
We can perform a Breadth-First Search (BFS) from both node1 and node2 to compute shortest distances to all other nodes. Since BFS is useful for finding shortest paths in unweighted graphs, it suits our needs in this problem.
By storing distances from both starting nodes in separate arrays and iterating through all nodes, we can find the node minimizing the maximum of both distances.
from collections import deque
class Solution:
def bfs(self, edges, start):
n = len(edges)
dist = [-1] * n
queue = deque([start])
dist[start] = 0
while queue:
node = queue.popleft()
next_node = edges[node]
if next_node != -1 and dist[next_node] == -1:
dist[next_node] = dist[node] + 1
queue.append(next_node)
return dist
def canMeet(self, dist1, dist2, n):
minDist = float('inf')
result = -1
for i in range(n):
if dist1[i] != -1 and dist2[i] != -1:
maxDist = max(dist1[i], dist2[i])
if maxDist < minDist:
minDist = maxDist
result = i
return result
def closestMeetingNode(self, edges, node1, node2):
n = len(edges)
dist1 = self.bfs(edges, node1)
dist2 = self.bfs(edges, node2)
return self.canMeet(dist1, dist2, n)import java.util.*;
class Solution {
public int[] bfs(int[] edges, int start) {
int n = edges.length;
int[] dist = new int[n];
Arrays.fill(dist, -1);
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
dist[start] = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
int nextNode = edges[node];
if (nextNode != -1 && dist[nextNode] == -1) {
dist[nextNode] = dist[node] + 1;
queue.add(nextNode);
}
}
return dist;
}
public int closestMeetingNode(int[] edges, int node1, int node2) {
int n = edges.length;
int[] dist1 = bfs(edges, node1);
int[] dist2 = bfs(edges, node2);
int minDist = Integer.MAX_VALUE;
int result = -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 < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
}
}#include <vector>
#include <queue>
#include <algorithm>
#include <limits.h>
class Solution {
public:
std::vector<int> bfs(const std::vector<int>& edges, int start) {
int n = edges.size();
std::vector<int> dist(n, -1);
std::queue<int> q;
q.push(start);
dist[start] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
int nextNode = edges[node];
if (nextNode != -1 && dist[nextNode] == -1) {
dist[nextNode] = dist[node] + 1;
q.push(nextNode);
}
}
return dist;
}
int closestMeetingNode(std::vector<int>& edges, int node1, int node2) {
int n = edges.size();
auto dist1 = bfs(edges, node1);
auto dist2 = bfs(edges, node2);
int minDist = INT_MAX;
int result = -1;
for (int i = 0; i < n; ++i) {
if (dist1[i] != -1 && dist2[i] != -1) {
int maxDist = std::max(dist1[i], dist2[i]);
if (maxDist < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
}
};var closestMeetingNode = function(edges, node1, node2) {
const bfs = (start) => {
const n = edges.length;
const dist = new Array(n).fill(-1);
const queue = [start];
dist[start] = 0;
while (queue.length > 0) {
const node = queue.shift();
const nextNode = edges[node];
if (nextNode !== -1 && dist[nextNode] === -1) {
dist[nextNode] = dist[node] + 1;
queue.push(nextNode);
}
}
return dist;
}
const n = edges.length;
const dist1 = bfs(node1);
const dist2 = bfs(node2);
let minDist = Infinity;
let result = -1;
for (let i = 0; i < n; i++) {
if (dist1[i] !== -1 && dist2[i] !== -1) {
const maxDist = Math.max(dist1[i], dist2[i]);
if (maxDist < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
};using System;
using System.Collections.Generic;
public class Solution {
public int[] Bfs(int[] edges, int start) {
int n = edges.Length;
int[] dist = new int[n];
Array.Fill(dist, -1);
Queue<int> queue = new Queue<int>();
queue.Enqueue(start);
dist[start] = 0;
while (queue.Count > 0) {
int node = queue.Dequeue();
int nextNode = edges[node];
if (nextNode != -1 && dist[nextNode] == -1) {
dist[nextNode] = dist[node] + 1;
queue.Enqueue(nextNode);
}
}
return dist;
}
public int ClosestMeetingNode(int[] edges, int node1, int node2) {
int n = edges.Length;
int[] dist1 = Bfs(edges, node1);
int[] dist2 = Bfs(edges, node2);
int minDist = int.MaxValue;
int result = -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 < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
}
}This Python solution uses BFS to determine the shortest path from node1 and node2 to all nodes in the graph. After this, it calculates the minimum of the maximum distances encountered and returns the index of the node meeting the criteria.
Time Complexity: O(n) since each node is processed in the queue at most once.
Space Complexity: O(n) for storing distances.
Approach 2: Approach 2: DFS for Shortest Path and Avoiding Cycles
Depth-First Search (DFS) can be leveraged to explore the graph while marking visited nodes to avoid cycles. This approach tracks distances from node1 and node2 in separate arrays, similarly to BFS but engages DFS mechanics.
class Solution:
def dfs(self, edges, start, dist, visited):
node = start
distance = 0
while node != -1 and node not in visited:
visited.add(node)
dist[node] = distance
node = edges[node]
distance += 1
def closestMeetingNode(self, edges, node1, node2):
n = len(edges)
dist1 = [-1] * n
dist2 = [-1] * n
self.dfs(edges, node1, dist1, set())
self.dfs(edges, node2, dist2, set())
minDist = float('inf')
result = -1
for i in range(n):
if dist1[i] != -1 and dist2[i] != -1:
maxDist = max(dist1[i], dist2[i])
if maxDist < minDist:
minDist = maxDist
result = i
return resultimport java.util.*;
class Solution {
public void dfs(int[] edges, int start, int[] dist, Set<Integer> visited) {
int node = start;
int distance = 0;
while (node != -1 && !visited.contains(node)) {
visited.add(node);
dist[node] = distance++;
node = edges[node];
}
}
public int closestMeetingNode(int[] edges, int node1, int node2) {
int n = edges.length;
int[] dist1 = new int[n], dist2 = new int[n];
Arrays.fill(dist1, -1);
Arrays.fill(dist2, -1);
Set<Integer> visited = new HashSet<>();
dfs(edges, node1, dist1, visited);
visited.clear();
dfs(edges, node2, dist2, visited);
int minDist = Integer.MAX_VALUE;
int result = -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 < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
}
}#include <vector>
#include <unordered_set>
#include <limits.h>
class Solution {
public:
void dfs(std::vector<int>& edges, int start, std::vector<int>& dist, std::unordered_set<int>& visited) {
int node = start;
int distance = 0;
while (node != -1 && visited.find(node) == visited.end()) {
visited.insert(node);
dist[node] = distance;
node = edges[node];
++distance;
}
}
int closestMeetingNode(std::vector<int>& edges, int node1, int node2) {
int n = edges.size();
std::vector<int> dist1(n, -1), dist2(n, -1);
std::unordered_set<int> visited;
dfs(edges, node1, dist1, visited);
visited.clear();
dfs(edges, node2, dist2, visited);
int minDist = INT_MAX;
int result = -1;
for (int i = 0; i < n; ++i) {
if (dist1[i] != -1 && dist2[i] != -1) {
int maxDist = std::max(dist1[i], dist2[i]);
if (maxDist < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
}
};var closestMeetingNode = function(edges, node1, node2) {
const dfs = (start, dist, visited) => {
let node = start;
let distance = 0;
while (node !== -1 && !visited.has(node)) {
visited.add(node);
dist[node] = distance++;
node = edges[node];
}
}
const n = edges.length;
const dist1 = new Array(n).fill(-1);
const dist2 = new Array(n).fill(-1);
const visited1 = new Set();
dfs(node1, dist1, visited1);
const visited2 = new Set();
dfs(node2, dist2, visited2);
let minDist = Infinity;
let result = -1;
for (let i = 0; i < n; i++) {
if (dist1[i] !== -1 && dist2[i] !== -1) {
const maxDist = Math.max(dist1[i], dist2[i]);
if (maxDist < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
};using System;
using System.Collections.Generic;
public class Solution {
public void Dfs(int[] edges, int start, int[] dist, HashSet<int> visited) {
int node = start;
int distance = 0;
while (node != -1 && !visited.Contains(node)) {
visited.Add(node);
dist[node] = distance++;
node = edges[node];
}
}
public int ClosestMeetingNode(int[] edges, int node1, int node2) {
int n = edges.Length;
int[] dist1 = new int[n];
int[] dist2 = new int[n];
Array.Fill(dist1, -1);
Array.Fill(dist2, -1);
var visited = new HashSet<int>();
Dfs(edges, node1, dist1, visited);
visited.Clear();
Dfs(edges, node2, dist2, visited);
int minDist = int.MaxValue;
int result = -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 < minDist) {
minDist = maxDist;
result = i;
}
}
}
return result;
}
}This Python solution uses DFS to explore graphs from two nodes, calculating visiting distances and determining the optimal meeting node that minimizes the maximal distance.
Time Complexity: O(n) since every node is processed once.
Space Complexity: O(n) for the distance and visited sets.
Approach 3: 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.
The complexity is O(n), and the space complexity is O(n), where n is the number of nodes.
Related problems:
function closestMeetingNode(edges: number[], node1: number, node2: number): number {
const n = edges.length;
const g = Array.from({ length: n }, () => []);
for (let i = 0; i < n; ++i) {
if (edges[i] != -1) {
g[i].push(edges[i]);
}
}
const inf = 1 << 30;
const f = (i: number) => {
const dist = new Array(n).fill(inf);
dist[i] = 0;
const q: number[] = [i];
while (q.length) {
i = q.shift();
for (const j of g[i]) {
if (dist[j] == inf) {
dist[j] = dist[i] + 1;
q.push(j);
}
}
}
return dist;
};
const d1 = f(node1);
const d2 = f(node2);
let ans = -1;
let d = inf;
for (let i = 0; i < n; ++i) {
const t = Math.max(d1[i], d2[i]);
if (t < d) {
d = t;
ans = i;
}
}
return ans;
}func closestMeetingNode(edges []int, node1 int, node2 int) int {
n := len(edges)
g := make([][]int, n)
for i, j := range edges {
if j != -1 {
g[i] = append(g[i], j)
}
}
const inf int = 1 << 30
f := func(i int) []int {
dist := make([]int, n)
for j := range dist {
dist[j] = inf
}
dist[i] = 0
q := []int{i}
for len(q) > 0 {
i = q[0]
q = q[1:]
for _, j := range g[i] {
if dist[j] == inf {
dist[j] = dist[i] + 1
q = append(q, j)
}
}
}
return dist
}
d1 := f(node1)
d2 := f(node2)
ans, d := -1, inf
for i, a := range d1 {
b := d2[i]
t := max(a, b)
if t < d {
d = t
ans = i
}
}
return ans
}class Solution {
func closestMeetingNode(_ edges: [Int], _ node1: Int, _ node2: Int) -> Int {
let n = edges.count
var g = [[Int]](repeating: [], count: n)
for i in 0..<n {
if edges[i] != -1 {
g[i].append(edges[i])
}
}
let inf = 1 << 30
func f(_ i: Int) -> [Int] {
var dist = [Int](repeating: inf, count: n)
dist[i] = 0
var q = [i]
var idx = 0
while idx < q.count {
let i = q[idx]
idx += 1
for j in g[i] {
if dist[j] == inf {
dist[j] = dist[i] + 1
q.append(j)
}
}
}
return dist
}
let d1 = f(node1)
let d2 = f(node2)
var ans = -1, d = inf
for i in 0..<n {
let t = max(d1[i], d2[i])
if t < d {
d = t
ans = i
}
}
return ans
}
}use std::collections::VecDeque;
impl Solution {
pub fn closest_meeting_node(edges: Vec<i32>, node1: i32, node2: i32) -> i32 {
let n = edges.len();
let mut g = vec![Vec::new(); n];
for i in 0..n {
if edges[i] != -1 {
g[i].push(edges[i] as usize);
}
}
let inf = 1 << 30;
let f = |mut i: usize| -> Vec<i32> {
let mut dist = vec![inf; n];
dist[i] = 0;
let mut q = VecDeque::new();
q.push_back(i);
while !q.is_empty() {
i = q.pop_front().unwrap();
for &j in &g[i] {
if dist[j] == inf {
dist[j] = dist[i] + 1;
q.push_back(j);
}
}
}
dist
};
let d1 = f(node1 as usize);
let d2 = f(node2 as usize);
let mut ans = -1;
let mut d = inf;
for i in 0..n {
let t = std::cmp::max(d1[i], d2[i]);
if t < d {
d = t;
ans = i as i32;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: BFS for Shortest Path | Time Complexity: O(n) since each node is processed in the queue at most once. |
| Approach 2: DFS for Shortest Path and Avoiding Cycles | Time Complexity: O(n) since every node is processed once. |
| BFS + Enumerate Common Nodes | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS for Shortest Path | O(n) | O(n) | Best general solution for shortest distance in an unweighted directed graph |
| DFS with Cycle Avoidance | O(n) | O(n) | Useful when implementing recursive traversal or explicitly handling cycles |
Frequently asked questions
Is Find Closest Node to Given Two Nodes easy or hard?
The problem is rated Medium because it requires recognizing the shortest-path pattern in a constrained directed graph. The implementation is straightforward once you compute distances from both starting nodes and compare them correctly.
Find Closest Node to Given Two Nodes Python/Java solution
Most implementations compute two distance arrays using BFS or DFS and then scan for the best node. Python and Java solutions typically store distances in arrays initialized to -1 and update them during traversal before performing the final comparison step.
How to solve Find Closest Node to Given Two Nodes in O(n)?
Traverse the graph starting from node1 and record distances to all reachable nodes. Repeat the traversal from node2 to compute a second distance array. Iterate through every node and pick the index that minimizes max(dist1[i], dist2[i]) while ignoring nodes unreachable from either source.
What is the best approach for Find Closest Node to Given Two Nodes?
The best approach computes the shortest distance from both node1 and node2 to every other node using BFS-style traversal. After building two distance arrays, iterate through all nodes and choose the node that minimizes max(dist1[i], dist2[i]). This runs in O(n) time and ensures the optimal meeting node is selected.
Is Find Closest Node to Given Two Nodes asked at Google/Amazon/Meta?
Problems involving shortest paths and graph traversal frequently appear in interviews at companies like Amazon, Google, and Meta. This question tests understanding of directed graphs, distance tracking, and handling cycles, which are common graph interview patterns.
What data structure is used in Find Closest Node to Given Two Nodes?
The solution uses arrays to store distances and standard graph traversal techniques such as BFS or DFS. Since each node has at most one outgoing edge, the graph can also be treated like a collection of linked chains with possible cycles.
What is the time complexity of Find Closest Node to Given Two Nodes?
The optimal solution runs in O(n) time because each node is visited at most once from node1 and once from node2. The final scan through all nodes to compute the minimum maximum distance also takes O(n). Space complexity is O(n) for storing the distance arrays.