diff options
author | Jack Sangdahl <[email protected]> | 2025-05-29 19:14:54 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-29 19:14:54 -0600 |
commit | 7db4171c577af30b3febdb6bea1a048eedee9ac3 (patch) | |
tree | d97ed8003d4bb67baf302d94f7a456a4efbe1d72 | |
parent | a950959b8a433478ab7a33b34fb1f4d2d7bafcb8 (diff) | |
download | leetcode-7db4171c577af30b3febdb6bea1a048eedee9ac3.tar.gz leetcode-7db4171c577af30b3febdb6bea1a048eedee9ac3.zip |
2359. find closest node to given two nodes
-rw-r--r-- | closest_node_2_nodes.c | 78 | ||||
-rw-r--r-- | closest_node_2_nodes.py | 46 |
2 files changed, 83 insertions, 41 deletions
diff --git a/closest_node_2_nodes.c b/closest_node_2_nodes.c index 85801e9..444505c 100644 --- a/closest_node_2_nodes.c +++ b/closest_node_2_nodes.c @@ -1,50 +1,46 @@ // 2359. Find Closest Node to Given Two Nodes -#include <limits.h> -#include <math.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> +#include "leetcode.h" -int closestMeetingNode(int *edges, int edgesSize, int node1, int node2) { - int n = edgesSize, *path1 = malloc(n * sizeof(int)), - *path2 = malloc(n * sizeof(int)); - memset(path1, -1, n * sizeof(int)); - memset(path2, -1, n * sizeof(int)); - int p = node1, step = 0; - while (1) { - path1[p] = step; - step++; - p = edges[p]; - if (p == -1) - break; - if (path1[p] != -1) - break; +/* + * 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 indes 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 minimised + */ + +void dfs(int node, int dist, int *edge, int *n) { + while (node != -1 && n[node] == -1) { + n[node] = dist++; + node = edge[node]; } - p = node2; - step = 0; - while (1) { - path2[p] = step; - step++; - p = edges[p]; - if (p == -1) - break; - if (path2[p] != -1) - break; +} + +int closestMeetingNode(int *edges, int edgesSize, int node1, int node2) { + int ans = -1, dist = INT_MAX; + int *n1 = (int *)malloc(edgesSize * sizeof(int)); + int *n2 = (int *)malloc(edgesSize * sizeof(int)); + for (int i = 0; i < edgesSize; i++) { + n1[i] = -1; + n2[i] = -1; } - int min = INT_MAX, ans = -1; - for (int i = 0; i < n; i++) - if (path1[i] != -1 && path2[i] != -1) - if (fmax(path1[i], path2[i]) < min) { - min = fmax(path1[i], path2[i]); - ans = i; - } - free(path1); - free(path2); + dfs(node1, 0, edges, n1); + dfs(node2, 0, edges, n2); + for (int i = 0; i < edgesSize; ++i) + if (fmin(n1[i], n2[i]) >= 0 && fmax(n1[i], n2[i]) < dist) { + dist = fmax(n1[i], n2[i]); + ans = i; + } + free(n1); + free(n2); return ans; } int main() { - int edges1[] = {2, 2, 3, -1}, edges2[] = {1, 2, -1}; - printf("%d\n", closestMeetingNode(edges1, 3, 0, 2)); // expect: 2 - printf("%d\n", closestMeetingNode(edges2, 3, 0, 2)); // expect: 2 + int e1[] = {2, 2, 3, -1}, e2[] = {1, 2, -1}; + printf("%d\n", closestMeetingNode(e1, ARRAY_SIZE(e1), 0, 1)); // expect: 2 + printf("%d\n", closestMeetingNode(e2, ARRAY_SIZE(e2), 0, 2)); // expect: 2 } diff --git a/closest_node_2_nodes.py b/closest_node_2_nodes.py new file mode 100644 index 0000000..a271f84 --- /dev/null +++ b/closest_node_2_nodes.py @@ -0,0 +1,46 @@ +# 2359. Find Closest Node to Given Two Nodes + +""" +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 indes 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 minimised +""" + + +class Solution(object): + def dfs(self, node, edges, dist, vis): + vis[node] = True + neigh = edges[node] + if neigh != -1 and vis[neigh] == False: + dist[neigh] = dist[node] + 1 + self.dfs(neigh, edges, dist, vis) + + def closestMeetingNode(self, edges, node1, node2): + """ + :type edges: List[int] + :type node1: int + :type node2: int + :rtype: int + """ + n, ans = len(edges), -1 + min_dist = float("inf") + n1, n2 = [0] * n, [0] * n + v1, v2 = [False] * n, [False] * n + self.dfs(node1, edges, n1, v1) + self.dfs(node2, edges, n2, v2) + for i in range(n): + if v1[i] and v2[i] and min_dist > max(n1[i], n2[i]): + min_dist = max(n1[i], n2[i]) + ans = i + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.closestMeetingNode(edges=[2, 2, 3, -1], node1=0, node2=1)) + print(obj.closestMeetingNode(edges=[1, 2, -1], node1=0, node2=2)) |