MediumNo. 2359
Find Closest Node to Given Two Nodes — LeetCode 2359 Python Solution
- Pattern
- Depth-First Search
- Topics
- Depth-First Search, Graph
- Reading time
- 5 min
- Source
- leetcode.com
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].
Example
- 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.
Python solution
class Solution:
def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
def f(i):
dist = [inf] * n
dist[i] = 0
q = deque([i])
while q:
i = q.popleft()
for j in g[i]:
if dist[j] == inf:
dist[j] = dist[i] + 1
q.append(j)
return dist
g = defaultdict(list)
for i, j in enumerate(edges):
if j != -1:
g[i].append(j)
n = len(edges)
d1 = f(node1)
d2 = f(node2)
ans, d = -1, inf
for i, (a, b) in enumerate(zip(d1, d2)):
if (t := max(a, b)) < d:
d = t
ans = i
return ansComplexity
- Time
- O(V+E)
- Space · auxiliary
- O(n)where n is the number of nodes
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2359. Find Closest Node to Given Two Nodes is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Depth-First Search and Graph.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2360 | Longest Cycle in a Graph | Hard |
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0332 | Reconstruct Itinerary | Hard |
| 0399 | Evaluate Division | Medium |
Frequently asked questions
- How hard is LeetCode 2359. Find Closest Node to Given Two Nodes?
LeetCode 2359. Find Closest Node to Given Two Nodes is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2359. Find Closest Node to Given Two Nodes?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 2359. Find Closest Node to Given Two Nodes?
The Python solution on this page uses O(n), where n is the number of nodes auxiliary space.
- What topics does LeetCode 2359. Find Closest Node to Given Two Nodes cover?
LeetCode 2359. Find Closest Node to Given Two Nodes is tagged Depth-First Search and Graph on LeetCode.