Leetcode 2359: Find Closest Node to Given Two Nodes
You are given a directed graph with n nodes, where each node can have at most one outgoing edge. You are provided with an array
edges representing the graph, where edges[i] indicates a directed edge from node i to node edges[i] (or -1 if there is no outgoing edge). You are also given two nodes node1 and node2. The task is to return the node that is reachable from both node1 and node2, such that the maximum of the distances from node1 and node2 to that node is minimized. If there are multiple such nodes, return the smallest index, or return -1 if no such node exists.Problem
Approach
Steps
Complexity
Input: The input consists of the following elements: an array `edges` of size n (1 <= n <= 10^5) representing the graph, and two integers `node1` and `node2` (0 <= node1, node2 < n).
Example: edges = [1, 2, -1], node1 = 0, node2 = 2
Constraints:
• 2 <= n <= 10^5
• -1 <= edges[i] < n
• edges[i] != i
• 0 <= node1, node2 < n
Output: Return the index of the node that can be reached from both `node1` and `node2` with the minimized maximum distance, or -1 if no such node exists.
Example: Output: 2
Constraints:
• Return the node index with the smallest maximum distance.
Goal: The goal is to find the node that minimizes the maximum distance from both `node1` and `node2` to that node.
Steps:
• Perform Depth-First Search (DFS) to calculate the distance from `node1` and `node2` to all other nodes.
• Iterate through all nodes, calculate the maximum distance for each node, and track the smallest such maximum.
Goal: The graph can contain cycles and may have up to 10^5 nodes. Ensure that your solution handles large inputs efficiently.
Steps:
• The graph may contain cycles.
• Nodes are indexed from 0 to n-1.
Assumptions:
• The graph may contain cycles, but each node has at most one outgoing edge.
• There is no self-loop (edges[i] != i).
• Input: edges = [2, 2, 3, -1], node1 = 0, node2 = 1
• Explanation: The possible distances to nodes from `node1` and `node2` are compared. The maximum of the distances to each node is calculated, and node 2 minimizes this value.
Approach: We can use DFS to calculate the distances from both `node1` and `node2` to all other nodes, and then find the node that minimizes the maximum distance.
Observations:
• We need to calculate the distance from `node1` and `node2` to each other node in the graph.
• The maximum of these two distances for each node should be minimized.
• The distance for a node can be computed with a DFS traversal. By storing the distances from both `node1` and `node2`, we can easily compute the desired result.
Steps:
• Perform DFS from `node1` and `node2` to get the distances to all other nodes.
• Iterate over all nodes, compute the maximum of the two distances, and track the minimum of these maximum distances.
Empty Inputs:
• Empty graph (n = 0) is not possible due to constraints.
Large Inputs:
• Ensure the solution is efficient for large graphs with up to 10^5 nodes.
Special Values:
• Cycles in the graph may cause nodes to be revisited multiple times.
Constraints:
• Make sure to handle graphs with cycles and ensure that DFS terminates properly in such cases.
void dfs(int node, vector<int> &edge, vector<int> &vis, int x) {
vis[node] = x;
if(edge[node] != -1 && vis[edge[node]] == -1)
dfs(edge[node], edge, vis, x + 1);
}
int closestMeetingNode(vector<int>& edges, int node1, int node2) {
int n = edges.size();
vector<int> dist1(n, -1);
dfs(node1, edges, dist1, 0);
vector<int> dist2(n, -1);
dfs(node2, edges, dist2, 0);
int dist, ans = -1, sol = INT_MAX;
for(int i = 0; i < n; i++) {
if(dist1[i] == -1 || dist2[i] == -1)
continue;
else
dist = max(dist1[i], dist2[i]);
if(dist < sol) {
sol = dist;
ans = i;
}
}
return ans;
}
1 : Function Definition
void dfs(int node, vector<int> &edge, vector<int> &vis, int x) {
This function performs a DFS traversal starting from the given node. It marks each node with a distance value 'x' to track the distance from the starting node.
2 : Action
vis[node] = x;
Mark the current node with the distance 'x' in the visitation array.
3 : Condition
if(edge[node] != -1 && vis[edge[node]] == -1)
If the current node has a neighbor and the neighbor has not been visited yet, perform DFS on that neighbor.
4 : Recursive Call
dfs(edge[node], edge, vis, x + 1);
Recursively call DFS for the neighbor node, incrementing the distance 'x' by 1.
5 : Function Definition
int closestMeetingNode(vector<int>& edges, int node1, int node2) {
This function finds the closest node where both node1 and node2 can meet by calculating their respective distances from every other node.
6 : Variable Initialization
int n = edges.size();
Store the size of the edges array, which represents the number of nodes in the graph.
7 : Variable Initialization
vector<int> dist1(n, -1);
Create an array to store the distances for node1, initializing all values to -1 (indicating that no nodes have been visited yet).
8 : Function Call
dfs(node1, edges, dist1, 0);
Call the DFS function for node1 to calculate its distance to all other nodes.
9 : Variable Initialization
vector<int> dist2(n, -1);
Create an array to store the distances for node2, initializing all values to -1.
10 : Function Call
dfs(node2, edges, dist2, 0);
Call the DFS function for node2 to calculate its distance to all other nodes.
11 : Variable Initialization
int dist, ans = -1, sol = INT_MAX;
Initialize variables to store the maximum distance ('dist') and the node with the smallest distance ('ans').
12 : Loop
for(int i = 0; i < n; i++) {
Iterate over all nodes to find the closest meeting node.
13 : Condition
if(dist1[i] == -1 || dist2[i] == -1)
Skip nodes that are not reachable by either node1 or node2.
14 : Action
continue;
If a node is unreachable by either of the nodes, continue to the next iteration.
15 : Else Block
else
If the node is reachable by both node1 and node2.
16 : Distance Calculation
dist = max(dist1[i], dist2[i]);
Calculate the maximum of the two distances (the furthest distance for each node) to determine the meeting point.
17 : Condition
if(dist < sol) {
If the calculated distance is smaller than the previous solution, update the solution.
18 : Action
sol = dist;
Update the smallest distance.
19 : Action
ans = i;
Store the current node as the best meeting point.
20 : Return Statement
return ans;
Return the node with the smallest maximum distance, which is the closest meeting point.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each DFS traversal takes O(n), and iterating through the nodes also takes O(n).
Best Case: O(n)
Worst Case: O(n)
Description: We need O(n) space to store the distances from both `node1` and `node2`.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus