Find Closest Node to Two Other Nodes - codepath/compsci_guides GitHub Wiki

Unit 12 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Graph Traversal, Single-Source Shortest Path

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • What happens if one of the nodes cannot reach any other node?

    • If both node1 and node2 cannot reach any common node, return -1.

  • How do we break ties if multiple nodes have the same maximum distance?

    • Return the node with the smallest index.

  • What if there are cycles in the graph?

    • Cycles are allowed, but we stop once we encounter a visited node to avoid infinite loops.
HAPPY CASE
Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Explanation: Both nodes 0 and 1 can reach node 2 with a distance of 1.

Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Explanation: Node 0 can reach 2 in 2 steps, and node 2 can reach itself in 0 steps.

EDGE CASE
Input: edges = [-1,-1,-1], node1 = 0, node2 = 2
Output: -1
Explanation: No nodes are reachable from either node.

Input: edges = [1,1,1], node1 = 0, node2 = 1
Output: 1
Explanation: Both nodes can only reach node 1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Graph Traversal or Shortest Path.

For Graph Traversal Problems, consider the following approaches:

  • BFS/DFS for Distance Calculation: Use BFS or simple iteration to compute the distances from each node.
  • Two Distance Arrays: Store the distances from both node1 and node2 to all other nodes.
  • Handling Cycles: Stop traversal when a node has already been visited to prevent cycles.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Approach:

  1. Calculate the distances from node1 to all reachable nodes using an iterative traversal.
  2. Calculate the distances from node2 similarly.
  3. Compare distances for each node to find the one with the minimum maximum distance.
  4. Return the node with the smallest index in case of ties.

Key Function:

  • calculate_distances(edges, start_node): Calculates distances from start_node to all other nodes.

Steps for Main Logic:

  1. Compute the distance arrays for both nodes.
  2. Traverse all nodes to find the minimum of the maximum distances.
  3. Handle ties by selecting the node with the smallest index.

4: I-mplement

Implement the code to solve the algorithm.

def calculate_distances(edges, start_node):
    n = len(edges)
    dist = [-1] * n  # Initialize distances as -1 (unreachable)
    current_node = start_node
    distance = 0

    while current_node != -1 and dist[current_node] == -1:
        dist[current_node] = distance
        current_node = edges[current_node]
        distance += 1
    
    return dist

def closest_meeting_node(edges, node1, node2):
    # Calculate distances from node1 and node2 to all other nodes
    dist_from_node1 = calculate_distances(edges, node1)
    dist_from_node2 = calculate_distances(edges, node2)

    min_distance = float('inf')
    result = -1

    # Iterate through all nodes and find the one with the minimum maximum distance
    for i in range(len(edges)):
        if dist_from_node1[i] != -1 and dist_from_node2[i] != -1:  # Both nodes can reach i
            max_dist = max(dist_from_node1[i], dist_from_node2[i])
            if max_dist < min_distance:
                min_distance = max_dist
                result = i
            elif max_dist == min_distance:
                result = min(result, i)  # Choose the smaller index in case of a tie

    return result

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

    • Distance from node1: [0, -1, 1, 2]
    • Distance from node2: [-1, 0, 1, 2]
    • Output: 2

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

    • Distance from node1: [0, 1, 2]
    • Distance from node2: [-1, -1, 0]
    • Output: 2

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

    • Output: -1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the number of nodes.

  • Time Complexity: O(n) because we traverse each node once for each starting node.
  • Space Complexity: O(n) for storing the distances from each node.