aboutsummaryrefslogtreecommitdiff
path: root/closest_node_2_nodes.c
diff options
context:
space:
mode:
Diffstat (limited to 'closest_node_2_nodes.c')
-rw-r--r--closest_node_2_nodes.c78
1 files changed, 37 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
}