Find Closest Node to Given Two Nodes - Practice Coding Problems

Find Closest Node to Given Two Nodes - 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]. 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: edges may contain cycles.

Input & Output

Example 1 — Basic Path

$ Input: edges = [2,1,3,-1], node1 = 0, node2 = 3

› Output: 2

💡 Note: From node 0: 0→2 (distance 1), from node 3: 3→2 (distance 1). Node 2 can be reached from both with max distance 1.

Example 2 — Linear Chain

$ Input: edges = [1,2,-1], node1 = 0, node2 = 2

› Output: 2

💡 Note: From node 0: 0→1→2 (distance 2), from node 2: 2 (distance 0). Node 2 has max distance 2.

Example 3 — No Common Node

$ Input: edges = [1,-1], node1 = 0, node2 = 1

› Output: -1

💡 Note: Node 0 can only reach node 1, but node 1 cannot reach any other nodes. No common reachable node exists.

Constraints

n == edges.length
2 ≤ n ≤ 10⁵
-1 ≤ edges[i] < n
edges[i] ≠ i
0 ≤ node1, node2 < n

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed graph with edges=[2,1,3,-1], node1=0, node2=3

Calculate Distances

Find distances from both starting nodes to all reachable nodes

Find Minimum

Return node with minimum maximum distance

Key Takeaway

🎯 Key Insight: Calculate distances from both starting nodes, then find the node that minimizes the maximum distance between them

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to find the node that minimizes the maximum distance from both starting points. The optimal approach uses two DFS traversals to compute distances from each starting node, then finds the meeting point with minimum maximum distance. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS for All Nodes	O(n²)	O(n)	Check every node to see if it's reachable from both starting nodes
Two-Pass Distance Calculation	O(n)	O(n)	Calculate distances from both starting nodes in separate passes, then find optimal meeting point

Brute Force DFS for All Nodes — Algorithm Steps

For each node in the graph
Run DFS from node1 to find distance
Run DFS from node2 to find distance
Track minimum of maximum distances

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Node 0

Calculate distances from both starting nodes

Check Node 1

Compare with previous best

Find Minimum

Return node with minimum maximum distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int dfs(int* edges, int n, int start, int target) {
    if (start == target) return 0;
    int* visited = calloc(n, sizeof(int));
    int distance = 0;
    int current = start;
    
    while (current != -1 && !visited[current]) {
        if (current == target) {
            free(visited);
            return distance;
        }
        visited[current] = 1;
        current = edges[current];
        distance++;
    }
    
    free(visited);
    return INT_MAX;
}

int solution(int* edges, int edgesSize, int node1, int node2) {
    int minMaxDist = INT_MAX;
    int result = -1;
    
    for (int i = 0; i < edgesSize; i++) {
        int dist1 = dfs(edges, edgesSize, node1, i);
        int dist2 = dfs(edges, edgesSize, node2, i);
        
        if (dist1 != INT_MAX && dist2 != INT_MAX) {
            int maxDist = (dist1 > dist2) ? dist1 : dist2;
            if (maxDist < minMaxDist) {
                minMaxDist = maxDist;
                result = i;
            }
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int edges[1000];
    int edgesSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        edges[edgesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int node1, node2;
    scanf("%d", &node1);
    scanf("%d", &node2);
    
    printf("%d\n", solution(edges, edgesSize, node1, node2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we run DFS which takes O(n) time in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

DFS recursion stack can go up to n nodes deep in worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS for All Nodes — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler