aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-29 19:14:54 -0600
committerJack Sangdahl <[email protected]>2025-05-29 19:14:54 -0600
commit7db4171c577af30b3febdb6bea1a048eedee9ac3 (patch)
treed97ed8003d4bb67baf302d94f7a456a4efbe1d72
parenta950959b8a433478ab7a33b34fb1f4d2d7bafcb8 (diff)
downloadleetcode-7db4171c577af30b3febdb6bea1a048eedee9ac3.tar.gz
leetcode-7db4171c577af30b3febdb6bea1a048eedee9ac3.zip
2359. find closest node to given two nodes
-rw-r--r--closest_node_2_nodes.c78
-rw-r--r--closest_node_2_nodes.py46
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))