aboutsummaryrefslogtreecommitdiff
path: root/closest_node_2_nodes.py
diff options
context:
space:
mode:
Diffstat (limited to 'closest_node_2_nodes.py')
-rw-r--r--closest_node_2_nodes.py46
1 files changed, 46 insertions, 0 deletions
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))