Skip to main content
Talentd

Find Closest Node to Given Two Nodes - Solution & Explanation

MediumDepth-First SearchGraph21 min readAsked at: Amazon, Google, Juspay +1
Practice this problem

Problem Statement

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.length
  • 2 <= n <= 105
  • -1 <= edges[i] < n
  • edges[i] != i
  • 0 <= 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.

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n) since each node is processed in the queue at most once.
Space Complexity: O(n) for storing distances.

Try this approach in the editor →

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.

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n) since every node is processed once.
Space Complexity: O(n) for the distance and visited sets.

Try this approach in the editor →

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:

Code

PythonJavaC++GoTypeScriptRustC#Swift

Python

Java

C++

Go

TypeScript

Rust

C#

Swift

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: BFS for Shortest Path

Time Complexity: O(n) since each node is processed in the queue at most once.
Space Complexity: O(n) for storing distances.

Approach 2: DFS for Shortest Path and Avoiding Cycles

Time Complexity: O(n) since every node is processed once.
Space Complexity: O(n) for the distance and visited sets.

BFS + Enumerate Common Nodes—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS for Shortest PathO(n)O(n)Best general solution for shortest distance in an unweighted directed graph
DFS with Cycle AvoidanceO(n)O(n)Useful when implementing recursive traversal or explicitly handling cycles

Video Solution

Find Closest Node to Given Two Nodes - Leetcode 2359 - Python • NeetCodeIO • 9,765 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find Closest Node to Given Two Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Validate Binary Search Tree