⚡Flashcard Drill➔
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

  1. Each node has at most one outgoing edge, so the graph is a functional graph -- paths are simple chains.
  2. Compute the distance from each start by walking the chain until it ends or revisits a node.
  3. For every node reachable from both, the cost is max(d1, d2).
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems