NeetCode #585LC-2359MediumGraphs
← Back to All Problems#585 · #2359 · Find Closest Node to Given Two Nodes(找到离给定两个节点最近的节点)
📌 Problem Statement & Constraints
You are given a directed graph where
edges[i] is the single outgoing edge from node i (-1 means none), and two starting nodes node1 and node2. Return the node reachable from both that minimises max(dist1, dist2); ties break by the smallest index. Return -1 if none. Constraints: 2 <= n <= 10^5.💡 Core Algorithmic Approaches
- Each node has at most one outgoing edge, so the graph is a functional graph -- paths are simple chains.
- Compute the distance from each start by walking the chain until it ends or revisits a node.
- For every node reachable from both, the cost is
max(d1, d2). - Pick the minimum cost, breaking ties by the smallest index.
💻 Benchmark Python3 Implementation
class Solution:
def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
n = len(edges)
def distances(start: int) -> List[int]:
d = [-1] * n
cur, step = start, 0
while cur != -1 and d[cur] == -1: # stop at the end or a revisit
d[cur] = step
cur = edges[cur]
step += 1
return d
d1 = distances(node1)
d2 = distances(node2)
best, best_cost = -1, float("inf")
for i in range(n):
if d1[i] != -1 and d2[i] != -1:
cost = max(d1[i], d2[i])
if cost < best_cost: # strict '<' keeps the smallest index
best_cost = cost
best = i
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each chain is walked once.
💾 Space Complexity
O(n) for the two distance arrays.
⚠️ Interview Pitfalls & Follow-ups
- Not stopping the walk on a revisit: a functional graph can contain a cycle.
- Computing distances with a general BFS: unnecessary -- each node has one outgoing edge.
- Using
<=when updating the best: that would keep the largest index on ties. - Requiring the node to be reachable in the same number of steps: the metric is
max(d1, d2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.