# 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.

## 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input `56`?

``````1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27``````
``````1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30``````
``````1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30``````

## 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:

1. 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.

2. `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`.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

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.

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

What's the output of running the following function using input `[30, 20, 10, 100, 33, 12]`?

``````1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8``````
``````1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12``````
``````1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85``````

### 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:

1. 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]`
2. 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]`
3. 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`.
4. 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.

5. 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) {
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)
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``````
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

## 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)`.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?