Find Closest Node to Given Two Nodes

Medium

Asked by:

26 views

Topics:

Graphs

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 that edges may contain cycles.

Example 1:

Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Explanation: The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1.
The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.

Example 2:

Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Explanation: The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0.
The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the graph, and can there be negative node values?
Is the graph guaranteed to be a directed acyclic graph (DAG), or could it contain cycles?
If either node1 or node2 is unreachable from any other node, or if there's no common ancestor, what should the function return?
If there are multiple nodes with the minimum combined distance to node1 and node2, can I return any one of them, or is there a specific criteria for selecting among them?
How should the graph be represented as input? Is it an adjacency list, adjacency matrix, or some other format?

Brute Force Solution

Approach

The brute force method for finding the closest node involves exploring all possible paths from each of the given nodes. We'll check every node to see which one is reachable from both starting points, and then find the closest among those.

Here's how the algorithm would work step-by-step:

Start from the first node and find every node that can be reached from it.
Separately, start from the second node and find every node that can be reached from it.
Now, compare the two sets of reachable nodes. Find the nodes that are in both sets; these are reachable from both starting nodes.
For each of these commonly reachable nodes, calculate the distance from the first starting node, and also the distance from the second starting node.
Add these two distances together to get the total distance for each commonly reachable node.
Finally, find the commonly reachable node with the smallest total distance. This is the closest node to both starting nodes.

Code Implementation

def find_closest_node_brute_force(edges, node1, node2):
    number_of_nodes = len(edges)
    
    def bfs(start_node):
        reachable_nodes = set()
        queue = [start_node]
        reachable_nodes.add(start_node)
        distances = {start_node: 0}
        
        while queue:
            current_node = queue.pop(0)
            
            neighbor = edges[current_node]
            if neighbor != -1:
                if neighbor not in reachable_nodes:
                    reachable_nodes.add(neighbor)
                    distances[neighbor] = distances[current_node] + 1
                    queue.append(neighbor)
        return reachable_nodes, distances
    
    # Find all reachable nodes and distances from node1
    reachable_from_node1, distances_from_node1 = bfs(node1)

    # Find all reachable nodes and distances from node2
    reachable_from_node2, distances_from_node2 = bfs(node2)
    
    # Identify common reachable nodes
    common_reachable_nodes = reachable_from_node1.intersection(reachable_from_node2)
    
    closest_node = -1
    min_total_distance = float('inf')
    
    # Find the closest node among common reachable nodes
    for node in common_reachable_nodes:

        #Calculate total distance from node1 and node2 to the common node
        total_distance = distances_from_node1[node] + distances_from_node2[node]
        
        if total_distance < min_total_distance:
            min_total_distance = total_distance
            closest_node = node
    
    return closest_node

Big(O) Analysis

Time Complexity

O(n²) – Finding reachable nodes from the first node takes O(n) time as we potentially traverse all n nodes. Similarly, finding reachable nodes from the second node also takes O(n). Comparing the two sets of reachable nodes, each potentially of size n, to find common nodes takes O(n * n). Calculating the distances from each of the starting nodes to each common node (again, up to n nodes) involves another O(n) operation. Finally, finding the minimum distance among these common nodes takes O(n), which is still dominated by the n * n comparison, resulting in a final time complexity of O(n²).

Space Complexity

O(N) – The algorithm uses sets to store reachable nodes from the first and second starting nodes. In the worst-case scenario, where all nodes are reachable from both starting nodes, each set could potentially store all N nodes of the graph, where N is the number of nodes in the graph. Additionally, calculating distances may require storing distances to each node. Therefore, the auxiliary space is proportional to the number of nodes, N. Thus, the space complexity is O(N).

Optimal Solution

Approach

We want to find the node closest to two starting nodes in a graph. Instead of blindly searching everywhere, we use a clever technique of mapping out how far each node is from each starting node and then finding the node where the distance from both is the least.

Here's how the algorithm would work step-by-step:

Starting from the first node, figure out how far away every other node is. Think of it like creating a map of distances from the first node to all others.
Do the same thing starting from the second node: create a similar map showing the distances from the second node to all other nodes.
Now, compare the two maps. For each node, add the distance from the first starting node to it, and the distance from the second starting node to it.
Find the node where this combined distance is the smallest. That node is the closest to both starting nodes.

Code Implementation

def find_closest_node(edges, node1, node2):
    number_of_nodes = len(edges)

    def get_distances(start_node):
        distances = [-1] * number_of_nodes
        distances[start_node] = 0
        queue = [start_node]

        while queue:
            current_node = queue.pop(0)
            neighbor = edges[current_node]

            if neighbor != -1 and distances[neighbor] == -1:
                distances[neighbor] = distances[current_node] + 1
                queue.append(neighbor)
        return distances

    # Calculate distances from node1 to all other nodes
    distances_from_node1 = get_distances(node1)

    # Calculate distances from node2 to all other nodes
    distances_from_node2 = get_distances(node2)

    min_distance_sum = float('inf')
    closest_node = -1

    # Find the node with the minimum sum of distances
    for current_node in range(number_of_nodes):

        distance_from_node1 = distances_from_node1[current_node]
        distance_from_node2 = distances_from_node2[current_node]

        if distance_from_node1 != -1 and distance_from_node2 != -1:

            combined_distance = distance_from_node1 + distance_from_node2

            # Keep track of the node with minimal distance sum
            if combined_distance < min_distance_sum:
                min_distance_sum = combined_distance
                closest_node = current_node

    return closest_node

Big(O) Analysis

Time Complexity

O(n) – Step 1 calculates the distances from the first starting node to all other nodes, which takes O(n) time because each node is visited and processed at most once using Breadth-First Search or Depth-First Search. Step 2 similarly computes distances from the second starting node, also in O(n) time. Step 3 iterates through all n nodes to sum the distances, taking O(n) time. Finally, finding the minimum distance in step 4 also involves iterating through all n nodes, thus taking O(n) time. Therefore, the overall time complexity is O(n) + O(n) + O(n) + O(n) which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses two dictionaries (or arrays) to store the distances from each starting node to all other nodes in the graph. Since the size of these dictionaries/arrays is proportional to the number of nodes in the graph, where N represents the number of nodes, the auxiliary space used is O(N) for each. Therefore the total space complexity of the algorithm is O(N). No additional significant space is used.

Edge Cases

Case	How to Handle
One or both input arrays are null or empty	Return -1 immediately, as no path can be found from non-existent nodes.
Arrays represent a graph with no edges at all (all values are -1)	Return -1 immediately since there will be no traversable paths from start nodes.
Start nodes are equal and point to the same reachable node	The algorithm should still correctly find the closest node to the single starting point.
One node is unreachable from its start node	The unreachable node should not contribute to the closest node calculation, and the algorithm should proceed with only the reachable nodes of the other start node.
Graph contains cycles	Use visited sets during BFS or DFS to prevent infinite loops and ensure termination.
Maximum sized input array potentially causing memory issues	Use an iterative approach (BFS) rather than recursion to avoid stack overflow and manage memory efficiently, or consider using generators.
Integer overflow when calculating distances	Use a data type that can accommodate large distances, such as long or BigInteger, if distances could exceed the maximum value of int.
No common node reachable from both start nodes	Return -1 since no valid meeting point exists between the two paths.

One or both input arrays are null or empty

How to Handle:

Return -1 immediately, as no path can be found from non-existent nodes.

Arrays represent a graph with no edges at all (all values are -1)

How to Handle:

Return -1 immediately since there will be no traversable paths from start nodes.

Start nodes are equal and point to the same reachable node

How to Handle:

The algorithm should still correctly find the closest node to the single starting point.

One node is unreachable from its start node

How to Handle:

The unreachable node should not contribute to the closest node calculation, and the algorithm should proceed with only the reachable nodes of the other start node.

Graph contains cycles

How to Handle:

Use visited sets during BFS or DFS to prevent infinite loops and ensure termination.

Maximum sized input array potentially causing memory issues

How to Handle:

Use an iterative approach (BFS) rather than recursion to avoid stack overflow and manage memory efficiently, or consider using generators.

Integer overflow when calculating distances

How to Handle:

Use a data type that can accommodate large distances, such as long or BigInteger, if distances could exceed the maximum value of int.

No common node reachable from both start nodes

How to Handle:

Return -1 since no valid meeting point exists between the two paths.