2359. Find Closest Node to Given Two Nodes

Problem Description

In this problem, we're given a directed graph that comprises n nodes labeled from 0 to n - 1. Each node in the graph has zero or one outgoing edge. A special array edges of length n represents the graph, where for each index i (representing a node), edges[i] is the end node of the outgoing edge from i. If edges[i] == -1, it indicates that there's no outgoing edge from node i.

Additionally, we're given two specific nodes: node1 and node2. Our objective is to find a node that both node1 and node2 can reach, and we want that node to be such that the longer of the two distances to this node (either from node1 or node2) is as small as possible. If there's more than one such node, we need to return the one with the smallest index. If no such node exists, we should return -1.

An important note is provided stating that there may be cycles in the graph created by these edges. This means that during our search for the target node, we might encounter loops where a node's outgoing edge leads to another node that indirectly has an outgoing edge leading back to the starting node.

Flowchart Walkthrough

Let's analyze Leetcode 2359. Find Closest Node to Given Two Nodes using the Flowchart. Here’s a guided breakdown based on the provided flowchart elements:

Is it a graph?

Yes: The problem explicitly states it's about finding the closest node in a directed graph.

Is it a tree?

Yes: The graph could be viewed as a tree structure where each node has an edge directed to exactly one other node, forming hierarchical relationships.

Is the problem related to directed acyclic graphs (DAGs)?

No: The focus of the problem is not on acyclicity or topological characteristics.

Is the problem related to shortest paths?

No: The essential query is finding the closest node to two given nodes, not necessarily the shortest path.

Does the problem involve connectivity?

Yes: We need to determine connectivity to find which nodes are closest to the given nodes.

Is the graph weighted?

No: The problem setup does not involve any weights on the edges; it is concerned only with direct connectivity and relative proximity.

Conclusion: According to the flowchart, using DFS would be appropriate here for exploring potential paths efficiently in an unweighted graph where connectivity plays a significant role. The Depth-First Search pattern can effectively traverse and check distances between nodes, helping determine the closest node to the given nodes.

Intuition

To solve this problem, we need to figure out the distance from node1 and node2 to all other nodes in the graph. In general, calculating the shortest distance in a graph is often done using Dijkstra's algorithm. However, because each node has at most one outgoing edge, the use of Dijkstra's algorithm could be an overkill. A simple depth-first or breadth-first search could suffice since there are no alternative paths to consider - each node has only one way to go.

Nonetheless, the provided solution uses Dijkstra's algorithm for some reason. This algorithm works by iteratively exploring the nearby nodes (neighbors) and updating the shortest known distance to every other node until all nodes have been considered.

Using Dijkstra's algorithm, we track the distance from node1 to all other nodes and store it in an array d1. Similarly, we calculate the distances from node2 to all other nodes and store these in another array d2.

After calculating these distances, we iterate over all the nodes to determine which node meets the problem's requirements. At each iteration, we check the maximum of the two distances (from node1 and node2) and compare it to the smallest maximum distance recorded so far. When we find a smaller maximum distance, we update our answer to that node's index.

By the end of our iteration, the ans variable should hold the index of the node that both node1 and node2 can reach and that minimizes the maximum of the two distances. If ans is unchanged from its initial value of -1, it means no such node exists, and we return -1 as required by the problem description.

Learn more about Depth-First Search and Graph patterns.

Solution Approach

The solution uses a modified version of Dijkstra's algorithm to find the shortest path from the starting nodes (node1 and node2) to all other nodes in the graph. Here's a walk-through of the implementation details:

Dijkstra's algorithm: This algorithm is typically used to find the shortest path from a single source to all other nodes in a graph. It's a greedy algorithm that selects the closest unvisited node at each step and updates the distances to its adjacent nodes.
dijkstra function: This is an inner function defined within the Solution class, which calculates the shortest distance from a given starting node to all other nodes. It initializes an array called dist with inf (infinity), which will hold the shortest distances from the starting node. The distance to the starting node itself is set to 0.
Priority Queue: A min-heap priority queue is used to keep track of the nodes to consider next based on their current distance from the starting node. Python's heapq module is used to implement the priority queue as a min-heap.
Graph representation: A defaultdict g is used to create a graph representation based on the edges array, where each key represents a node index, and its value is a list containing the single outgoing edge target.
Updating distances: At each step, the algorithm pops the node i with the smallest distance from the priority queue. Then, it looks at the outgoing edge from this node (if any) and checks if the distance to the destination node j can be improved. If dist[j] can be reduced by taking the edge i -> j, we update dist[j] and push the new distance and node j into the priority queue.
Distances from node1 and node2: Once the dijkstra function is well-defined, it's called twice - once with node1 and once with node2 as the starting node. The results are stored in d1 and d2 respectively, which are arrays holding the shortest distances from node1 and node2 to all other nodes.
Finding the meeting node: Finally, the solution iterates over all nodes and checks the maximum distance from either node1 or node2 to node i. This step determines which node is reachable from both starting nodes with the minimized longer path. It records the node index and the distance, if it's the smallest encountered so far. The use of t := max(a, b) inside the iteration is a Python assignment expression syntax (often called the "walrus operator") introduced in Python 3.8.
Returning the result: After inspecting all nodes, the index of the node with the minimum maximum distance is ans. If ans is still -1, no node meets the criteria, and -1 is returned, otherwise, the index of the appropriate meeting node is returned.

By using this implementation, we effectively find the closest meeting node from node1 and node2 or return -1 if no such meeting point exists.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we are given a graph represented by the edges array edges = [2, 2, 3, -1], and we need to find a meeting node for node1 = 0 and node2 = 1. This means our graph has the following outgoing edges:

Node 0 connects to node 2
Node 1 connects to node 2
Node 2 connects to node 3
Node 3 has no outgoing edge (-1)

Using the described solution approach:

Initialize distance arrays: Create two arrays d1 and d2 with distances initialized to infinity, except that d1[node1] and d2[node2] are set to 0. In our example:
- d1 = [0, inf, inf, inf]
- d2 = [inf, 0, inf, inf]
Run Dijkstra's for both nodes: Apply the modified Dijkstra's algorithm starting from node1 and node2:
- From node1 (0): We update the distance to the node it points to, d1[2] = 1, and since node 2 points to node 3, d1[3] = 2.
- From node2 (1): Similarly, d2[2] = 1, and subsequently, d2[3] = 2.
By the end of this process, the distance arrays are:
- d1 = [0, inf, 1, 2]
- d2 = [inf, 0, 1, 2]
Find the best meeting node: Iterate through each node to determine the maximum distance t from node1 or node2 and select the node with the smallest such maximum distance, preferring nodes with smaller indexes. We look for min(max(d1[i], d2[i])) for all i.
- For node 0, there's no path from node2, so we skip it.
- For node 1, there's no path from node1, so we skip it.
- For node 2, the maximum distance is max(1, 1) = 1.
- For node 3, the maximum distance is max(2, 2) = 2.
Selecting the result: The node with the smallest maximum distance encountered is node 2, with a maximum distance of 1. There are no other nodes with a smaller maximum distance.
Returning the result: The index of the meeting node with the smallest maximum distance from both node1 and node2 is 2. So, we return 2 as the answer.

In summary, using the small graph example with edges = [2, 2, 3, -1], and starting nodes node1 = 0 and node2 = 1, we find that both nodes can meet at node 2 with the minimized longest path, so the result is 2. If no such meeting node existed that both could reach, we would return -1.

Solution Implementation

1from heapq import heappop, heappush
2from collections import defaultdict
3from math import inf
4from typing import List
5
6class Solution:
7    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
8        # Define a Dijkstra's algorithm function to find shortest paths from a starting node
9        def dijkstra(start_node):
10            # Initialize distance array with infinity values
11            distances = [inf] * num_nodes
12            # Distance to the start node is 0
13            distances[start_node] = 0
14            # Priority queue for the Dijkstra algorithm, containing tuples of (distance, node)
15            priority_queue = [(0, start_node)]
16          
17            # Process the queue until it is empty
18            while priority_queue:
19                # Pop the node with the smallest distance from the queue
20                current_distance, current_node = heappop(priority_queue)
21                # Iterate over all adjacent nodes
22                for neighbor in graph[current_node]:
23                    # If a shorter path to the neighbor is found, update the distance and add it to the queue
24                    if distances[neighbor] > current_distance + 1:
25                        distances[neighbor] = current_distance + 1
26                        heappush(priority_queue, (distances[neighbor], neighbor))
27          
28            return distances
29
30        # Construct the graph using a default dictionary to hold adjacency lists
31        graph = defaultdict(list)
32        for i, neighbor in enumerate(edges):
33            if neighbor != -1:
34                graph[i].append(neighbor)
35      
36        # Count the number of nodes
37        num_nodes = len(edges)
38      
39        # Run Dijkstra's algorithm from both given nodes
40        distances_from_node1 = dijkstra(node1)
41        distances_from_node2 = dijkstra(node2)
42      
43        # Initialize the answer and the smallest maximum distance found
44        closest_meeting_node = -1
45        smallest_max_distance = inf
46      
47        # Iterate over each node to find the optimal meeting node
48        for i, (distance_node1, distance_node2) in enumerate(zip(distances_from_node1, distances_from_node2)):
49            # Compute the larger of the two distances
50            current_max_distance = max(distance_node1, distance_node2)
51          
52            # If this node has a smaller or equal max distance, it's a candidate
53            if current_max_distance < smallest_max_distance:
54                # Update the closest meeting node and the smallest maximum distance
55                smallest_max_distance = current_max_distance
56                closest_meeting_node = i
57      
58        # Return the index of the closest meeting node (or -1 if not found)
59        return closest_meeting_node
60
61# The method can be called on an instance of the Solution class.
62# For example:
63# solution = Solution()
64# result = solution.closestMeetingNode(edges, node1, node2)
65

1class Solution {
2    private int nodeCount; // Number of nodes in the graph
3    private List<Integer>[] graph; // Adjacency list representation of the graph
4
5    // Calculates the closest meeting node from two starting nodes in a directed graph
6    public int closestMeetingNode(int[] edges, int node1, int node2) {
7        nodeCount = edges.length;
8        graph = new List[nodeCount];
9      
10        // Initialize graph adjacency lists
11        Arrays.setAll(graph, x -> new ArrayList<>());
12      
13        // Build the graph from edge list representation
14        for (int i = 0; i < nodeCount; ++i) {
15            if (edges[i] != -1) {
16                graph[i].add(edges[i]);
17            }
18        }
19      
20        // Use Dijkstra's algorithm to find shortest paths from both starting nodes
21        int[] distancesFromNode1 = dijkstra(node1);
22        int[] distancesFromNode2 = dijkstra(node2);
23      
24        // Initialize the minimum distance and answer node index
25        int minDistance = Integer.MAX_VALUE;
26        int closestNode = -1;
27      
28        // Iterate through nodes to find the closest meeting node
29        for (int i = 0; i < nodeCount; ++i) {
30            int maxOfBothDistances = Math.max(distancesFromNode1[i], distancesFromNode2[i]);
31            if (maxOfBothDistances < minDistance) {
32                minDistance = maxOfBothDistances;
33                closestNode = i;
34            }
35        }
36        return closestNode;
37    }
38
39    // Dijkstra's algorithm to find shortest path distances from a starting node 'startNode'
40    private int[] dijkstra(int startNode) {
41        int[] distances = new int[nodeCount];
42      
43        // Initialize distances to a large number
44        Arrays.fill(distances, Integer.MAX_VALUE);
45        distances[startNode] = 0; // Distance to start node is zero
46      
47        // Priority queue to select the closest unvisited node in each step
48        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
49        priorityQueue.offer(new int[]{0, startNode});
50      
51        while (!priorityQueue.isEmpty()) {
52            int[] current = priorityQueue.poll();
53            int currentNode = current[1];
54          
55            // Explore neighbors and update distances
56            for (int neighbor : graph[currentNode]) {
57                if (distances[neighbor] > distances[currentNode] + 1) {
58                    distances[neighbor] = distances[currentNode] + 1;
59                    priorityQueue.offer(new int[]{distances[neighbor], neighbor});
60                }
61            }
62        }
63      
64        return distances; // Return array of distances from start node to all other nodes
65    }
66}
67

1class Solution {
2public:
3    // Function to find the closest meeting node between node1 and node2
4    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
5        // Get the total number of nodes
6        int numNodes = edges.size();
7        // Graph storage using adjacency list
8        vector<vector<int>> graph(numNodes);
9        // Constructing the adjacency list for the graph
10        for (int i = 0; i < numNodes; ++i) {
11            if (edges[i] != -1) {
12                graph[i].push_back(edges[i]);
13            }
14        }
15        // Define infinity as a large number
16        const int infinity = 1 << 30;
17        // Pair for holding distance and node information
18        using DistNodePair = pair<int, int>;
19
20        // Lambda function for Dijkstra's algorithm to find the shortest path
21        // from a starting node to all other nodes
22        auto dijkstra = [&](int startNode) {
23            // Initialize distances to infinity
24            vector<int> distances(numNodes, infinity);
25            // Distance to the start node is 0
26            distances[startNode] = 0;
27            // Min-heap priority queue to select the node with the smallest distance
28            priority_queue<DistNodePair, vector<DistNodePair>, greater<DistNodePair>> pq;
29            // Push the start node onto the queue
30            pq.emplace(0, startNode);
31            // Perform the algorithm until the queue is empty
32            while (!pq.empty()) {
33                // Get the top pair in the queue
34                auto pair = pq.top();
35                pq.pop();
36                int currentNode = pair.second;
37                // Update distances for adjacent nodes
38                for (int neighbor : graph[currentNode]) {
39                    if (distances[neighbor] > distances[currentNode] + 1) {
40                        distances[neighbor] = distances[currentNode] + 1;
41                        pq.emplace(distances[neighbor], neighbor);
42                    }
43                }
44            }
45            // Return the calculated distances
46            return distances;
47        };
48
49        // Get distances from node1 and node2 to all other nodes using Dijkstra's
50        vector<int> distancesFromNode1 = dijkstra(node1);
51        vector<int> distancesFromNode2 = dijkstra(node2);
52
53        // Variables to store the result and the minimum distance found
54        int closestNode = -1;
55        int minDistance = infinity;
56
57        // Look for the node that minimizes the maximum distance 
58        // from both node1 and node2
59        for (int i = 0; i < numNodes; ++i) {
60            int maxDist = max(distancesFromNode1[i], distancesFromNode2[i]);
61            if (maxDist < minDistance) {
62                minDistance = maxDist;
63                closestNode = i;
64            }
65        }
66        // Return the index of the closest meeting node
67        return closestNode;
68    }
69};
70

1function closestMeetingNode(edges: number[], node1: number, node2: number): number {
2    const numNodes = edges.length; // Number of nodes
3    const graph = Array.from({ length: numNodes }, () => []); // Graph representation
4
5    // Building the graph from edge list, assuming it's directed
6    for (let i = 0; i < numNodes; ++i) {
7        if (edges[i] !== -1) {
8            graph[i].push(edges[i]);
9        }
10    }
11
12    const infiniteDistance = 1 << 30; // A symbolic representation of infinity
13
14    // Function to calculate distances from a start node to all other nodes
15    const calculateDistances = (startNode: number): number[] => {
16        const distances = new Array(numNodes).fill(infiniteDistance);
17        distances[startNode] = 0;
18        const queue: number[] = [startNode];
19      
20        while (queue.length > 0) {
21            const currentNode = queue.shift();
22            for (const nextNode of graph[currentNode]) {
23                if (distances[nextNode] === infiniteDistance) {
24                    distances[nextNode] = distances[currentNode] + 1;
25                    queue.push(nextNode);
26                }
27            }
28        }
29        return distances;
30    };
31
32    // Calculate distances from both nodes to all other nodes
33    const distancesFromNode1 = calculateDistances(node1);
34    const distancesFromNode2 = calculateDistances(node2);
35  
36    let closest = -1; // The closest node initialized to -1 (indicating no such node)
37    let minDistance = infiniteDistance; // Start with infinite distance
38
39    // Find the closest meeting node
40    for (let i = 0; i < numNodes; ++i) {
41        const maxDistance = Math.max(distancesFromNode1[i], distancesFromNode2[i]);
42        // Update closest if a node with smaller maximum distance is found
43        if (maxDistance < minDistance) {
44            minDistance = maxDistance;
45            closest = i;
46        }
47    }
48  
49    return closest;
50}
51

Time and Space Complexity

The provided code defines a function that aims to find the node closest to both node1 and node2 from a graph represented by edges, where each edge is a directed connection from a node to another. It makes use of Dijkstra's algorithm to find the shortest path from each start node to all other nodes.

Time Complexity

The time complexity of the Dijkstra algorithm is O(V + E log V) where V is the number of vertices and E is the number of edges because each vertex is processed exactly once and each edge is considered once in the priority queue.

The original function runs two separate instances of Dijkstra's algorithm (one for each node), making the time complexity O(2(V + E log V)). However, the constant factor 2 does not impact the big-O notation, so we usually don't include it. Therefore, the time complexity simplifies to O(V + E log V).

In the worst-case scenario, the graph is a dense graph where E is close to V^2. However, since we are given a list of edges for each node that should represent a single next node (or -1 if there is no out-edge), the implied graph structure seems to be a directed graph where each node has at most one outgoing edge, which suggests E is at most V. Therefore, if we consider the graph representation implied by edges, the time complexity would be O(V log V).

Space Complexity

The space complexity of the function is determined by the space required for the graph representation (g), the distance arrays (d1 and d2), and the priority queue (q):

The graph g is a dictionary containing at most V key-value pairs if each node has an out-edge, which leads to O(V) space.
The two distance arrays d1 and d2 each require O(V) space as they hold a distance value for each node.
The priority queue q at any instance can hold at most V pairs (each pair consisting of a distance and a node index), yielding O(V) space.

The total space required is the sum of the spaces for these data structures, which leads to O(V + V + V) = O(3V). Again, we don't usually include constant factors in big-O notation, so the space complexity simplifies to O(V).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know