We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Closest Node to Given Two Nodes

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each node has at most one outgoing edge, simplifying traversal.
  • We need to compute the distance from both node1 and node2 to all reachable nodes.
  • The goal is to find a node that minimizes the maximum distance from both starting nodes.
  • The presence of cycles in the graph requires careful handling to avoid infinite loops.

Space and Time Complexity

Time Complexity: O(n) - We may have to traverse all nodes to determine distances. Space Complexity: O(n) - We use arrays to store distances for each node.

Solution

To solve the problem, we will use a depth-first search (DFS) or iterative traversal to compute the distances from both node1 and node2 to all other nodes. We will create two distance arrays, one for each node, to store the distance from each starting node to every other reachable node. After populating these arrays, we will iterate through all nodes and find the node that minimizes the maximum distance between the two starting nodes. If multiple nodes yield the same maximum distance, we will choose the one with the smallest index.

Code Solutions

def closestMeetingNode(edges, node1, node2):
    n = len(edges)

    def get_distances(start):
        distances = [-1] * n
        current = start
        distance = 0
        while current != -1 and distances[current] == -1:
            distances[current] = distance
            current = edges[current]
            distance += 1
        return distances

    dist1 = get_distances(node1)
    dist2 = get_distances(node2)

    min_max_distance = float('inf')
    result_node = -1

    for i in range(n):
        if dist1[i] != -1 and dist2[i] != -1:
            max_distance = max(dist1[i], dist2[i])
            if max_distance < min_max_distance or (max_distance == min_max_distance and i < result_node):
                min_max_distance = max_distance
                result_node = i

    return result_node
← Back to All Questions