Find Closest Node to Given Two Nodes — Problem & Solution
Find Closest Node to Given Two Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Closest Node to Given Two Nodes is a medium coding problem on depth-first search and graph, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Graph
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a directed graph of n nodes where each node has at most one outgoing edge: edges[i] is the node i points to, or -1.
Find a node reachable from both node1 and node2 that minimises the larger of the two distances. If several qualify, return the smallest index; if none exists, return -1.
Example 1
Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Example 2
Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Example 3
Input: edges = [-1,-1], node1 = 0, node2 = 1
Output: -1
Constraints
1 <= edges.length <= 40-1 <= edges[i] < edges.lengthedges[i] != i0 <= node1, node2 < edges.length
Hints for Find Closest Node to Given Two Nodes
Hint 1
From each start, follow the single outgoing edge and record the distance to every node you meet.
Hint 2
The walk ends at
-1or the moment it revisits a node, so it is linear.Hint 3
Scan the nodes reachable from both and keep the one with the smallest
max(d1, d2), breaking ties by index.
How to solve Find Closest Node to Given Two Nodes
Walk the single outgoing edge from each start recording distances, then pick the node reachable from both with the smallest max(d1, d2), ties to the smaller index.
Approach
walk(start)recordsdist[node] = stepsuntil-1or a repeat.- Scan
iin order; keep the firstiminimisingmax(d1[i], d2[i]).
Why it works
With one outgoing edge per node the reachable set is a simple path plus a cycle, so each walk is linear and records every reachable node's distance exactly.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Scanning indices in ascending order with a strict
<gives the smallest index on ties.
Reference solution
Python
def closestMeetingNode(edges, node1: int, node2: int) -> int:
def walk(start):
dist = [-1] * len(edges)
node, steps = start, 0
while node != -1 and dist[node] == -1:
dist[node] = steps
steps += 1
node = edges[node]
return dist
d1, d2 = walk(node1), walk(node2)
best, best_distance = -1, -1
for i in range(len(edges)):
if d1[i] == -1 or d2[i] == -1:
continue
worst = max(d1[i], d2[i])
if best == -1 or worst < best_distance:
best, best_distance = i, worst
return bestJava
private static int[] walkDistances(int[] edges, int start) {
int[] dist = new int[edges.length];
Arrays.fill(dist, -1);
int node = start, steps = 0;
while (node != -1 && dist[node] == -1) {
dist[node] = steps++;
node = edges[node];
}
return dist;
}
public static int closestMeetingNode(int[] edges, int node1, int node2) {
int[] d1 = walkDistances(edges, node1);
int[] d2 = walkDistances(edges, node2);
int best = -1, bestDistance = -1;
for (int i = 0; i < edges.length; i++) {
if (d1[i] == -1 || d2[i] == -1) continue;
int worst = Math.max(d1[i], d2[i]);
if (best == -1 || worst < bestDistance) {
best = i;
bestDistance = worst;
}
}
return best;
}C++
static vector<int> walkDistances(vector<int>& edges, int start) {
vector<int> dist(edges.size(), -1);
int node = start, steps = 0;
while (node != -1 && dist[node] == -1) {
dist[node] = steps++;
node = edges[node];
}
return dist;
}
int closestMeetingNode(vector<int>& edges, int node1, int node2) {
vector<int> d1 = walkDistances(edges, node1);
vector<int> d2 = walkDistances(edges, node2);
int best = -1, bestDistance = -1;
for (int i = 0; i < (int) edges.size(); i++) {
if (d1[i] == -1 || d2[i] == -1) continue;
int worst = max(d1[i], d2[i]);
if (best == -1 || worst < bestDistance) {
best = i;
bestDistance = worst;
}
}
return best;
}JavaScript
var closestMeetingNode = function(edges, node1, node2) {
const walk = function(start) {
const dist = [];
for (let i = 0; i < edges.length; i++) dist.push(-1);
let node = start, steps = 0;
while (node !== -1 && dist[node] === -1) {
dist[node] = steps++;
node = edges[node];
}
return dist;
};
const d1 = walk(node1);
const d2 = walk(node2);
let best = -1, bestDistance = -1;
for (let i = 0; i < edges.length; i++) {
if (d1[i] === -1 || d2[i] === -1) continue;
const worst = d1[i] > d2[i] ? d1[i] : d2[i];
if (best === -1 || worst < bestDistance) {
best = i;
bestDistance = worst;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure