Problem of the day: Leetcode 2359. Find Closest Node to Given Two Nodes

 2359. Find Closest Node to Given Two Nodes

515

117

Companies

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 <= 105
• -1 <= edges[i] < n
• edges[i] != i
• 0 <= node1, node2 < n

Solution

class Solution {

public:

    int closestMeetingNode(vector<int>& edges, int node1, int node2) {

        int n = edges.size();

        vector <bool> isVisited(n, false);

        vector <int> dp1(n, INT_MAX), dp2(n, INT_MAX);

        dp1[node1] = 0;

        int src = node1;

        while (edges[src] != -1 && isVisited[src] == false) {

            isVisited[src] = 1;

            int pred = src;

            src = edges[src];

            dp1[src] = min(dp1[src], dp1[pred] + 1);

        }

        

        isVisited = vector <bool> (n, false);

        dp2[node2] = 0;

        src = node2;

        while (edges[src] != -1 && isVisited[src] == false) {

            isVisited[src] = 1;

            int pred = src;

            src = edges[src];

            dp2[src] = min(dp2[src], dp2[pred] + 1);

        }

        

        int res = -1, tmp = INT_MAX;

        for (int i = 0; i < n; i++) {

            int max_val = max(dp1[i], dp2[i]);

            if (max_val < tmp && max_val != INT_MAX) {

                tmp = max_val;

                res = i;

            }

        }

        

        return res;

    }

};

The above solution is attempting to find the closest meeting point between two nodes in a directed graph. The graph is represented by an array of integers called edges where each element in the array represents the next node in the graph. The function closestMeetingNode(vector<int>& edges, int node1, int node2) takes in the graph represented by edges as well as the starting nodes node1 and node2 and returns an integer representing the closest meeting point between the two nodes.

The function uses several helper variables, including a vector isVisited of size n (where n is the size of the edges array), two vectors dp1 and dp2 of size n, and several integers n, src, pred, res, and tmp.

The function first sets the distance from node1 to each node in the graph to infinity and the distance from node1 to itself to 0. It then iterates through the graph using a while loop, starting at node1, and updating the distance from node1 to each node in the graph using the following logic: if the current node has not been visited yet and the next node in the graph exists, mark the current node as visited, set the distance from node1 to the next node as the minimum of the current distance and the distance from node1 to the current node + 1, and move on to the next node.

The function then repeats this process for node2, using the vector dp2 instead of dp1.

Finally, the function iterates through the graph again, and for each node it checks if the maximum distance from the node to both node1 and node2 is less than the current minimum distance, and if so, updates the minimum distance and the closest meeting point.

The function then returns the closest meeting point.