Find Closest Node to Given Two Nodes

Medium
465.

Find Closest Node to Given Two Nodes

Find Closest Node to Given Two Nodes is a medium coding problem on depth-first search and graph, asked in Amazon and Google interviews.

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.length
  • edges[i] != i
  • 0 <= node1, node2 < edges.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} edges
 * @param {number} node1
 * @param {number} node2
 * @return {number}
 */
var closestMeetingNode = function(edges, node1, node2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • edges[i] != i
  • 0 <= node1, node2 < edges.length

Hints for Find Closest Node to Given Two Nodes

  1. Hint 1

    From each start, follow the single outgoing edge and record the distance to every node you meet.

  2. Hint 2

    The walk ends at -1 or the moment it revisits a node, so it is linear.

  3. 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

  1. walk(start) records dist[node] = steps until -1 or a repeat.
  2. Scan i in order; keep the first i minimising max(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 best

Java

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