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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Closest Node to Given Two Nodes

Number: 2438

Difficulty: Medium

Paid? No

Companies: Juspay

Problem Description

Given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge (represented by the array edges), determine the node which is reachable from both node1 and node2 such that the maximum distance (steps required) from either node to that meeting node is minimized. If there are multiple candidates, return the one with the smallest index. If no such node exists, return -1.

Key Insights

  • Each node has at most one outgoing edge, so from any starting node you can perform a simple traversal (like following a linked list) until a cycle is detected or no further node exists.
  • Compute the distance from node1 and node2 to every other node along the reachable path.
  • Compare the distances for nodes reachable from both node1 and node2, and minimize the maximum distance across the two starting points.
  • Handle cycles by ensuring that once a node is visited the distance is fixed and not revisited.

Space and Time Complexity

Time Complexity: O(n) - Each traversal may visit each node at most once. Space Complexity: O(n) - Two arrays (or similar data structures) to store distances for node1 and node2.

Solution

We solve the problem by computing the distances from node1 and node2 to all other nodes using a simple traversal that stops when a node repeats or no further node is found (i.e., edge is -1). After these two traversals, we iterate through all nodes and for nodes that are reachable from both sources, we consider the maximum distance from node1 and node2. The node that minimizes this maximum distance (and in case of ties, the smallest index) is our answer.

Key data structures and approaches:

  • Arrays to store the distance from node1 and node2.
  • A while loop to traverse the unique path from the starting node.
  • A final loop to determine the optimal meeting node.

Code Solutions

# Function to find the closest meeting node in Python
def closestMeetingNode(edges, node1, node2):
    # Helper function to compute distances from the starting node to all reachable nodes
    def getDistances(start):
        distances = [-1] * len(edges)  # initialize distances with -1 (unreachable)
        distance = 0
        current = start
        # traverse until no further node or a cycle is detected
        while current != -1 and distances[current] == -1:
            distances[current] = distance  # set the distance for the current node
            current = edges[current]  # move to the next node using the directed edge
            distance += 1
        return distances
    
    # Get distances from node1 and node2 respectively
    distances1 = getDistances(node1)
    distances2 = getDistances(node2)
    
    result = -1  # default value if no valid meeting node is found
    bestMaxDistance = float("inf")  # store the minimal possible maximum distance
    
    # Check every node to see if it is reachable from both node1 and node2
    for i in range(len(edges)):
        if distances1[i] != -1 and distances2[i] != -1:
            # Maximum distance from the two sources
            currentMaxDistance = max(distances1[i], distances2[i])
            # If the current maximum distance is less than the best found, update result
            if currentMaxDistance < bestMaxDistance:
                bestMaxDistance = currentMaxDistance
                result = i
                
    return result

# Example usage:
# edges = [2, 2, 3, -1], node1 = 0, node2 = 1 should return 2
print(closestMeetingNode([2, 2, 3, -1], 0, 1))
← Back to All Questions