Find Closest Node to Given Two Nodes LeetCode solution in Python

1
# Runtime: 3032 ms (Top 5.02%) | Memory: 139.1 MB (Top 14.52%)
2
class Solution:
3
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
4

5
        res = float("inf")
6

7
        def dfs(node, arr, counter=0):
8

9
            # making sure we haven't visited the node before (i.e., value in the array != -1)
10
            while arr[node] == -1 and node != -1:
11

12
                # assigning how many moves it takes to reach node
13
                arr[node] = counter
14
                next_node = edges[node]
15

16
                # going through each neighbor if exists and updating the counter
17
                dfs(edges[node], arr, counter + 1)
18

19
            return arr
20

21
        # find moves to reach nodes from node1
22
        n1 = [-1 for i in range(len(edges))]
23
        dfs(node1, n1)
24

25
        # find moves to reach nodes from node2
26
        n2 = [-1 for i in range(len(edges))]
27
        dfs(node2, n2)
28

29
        answer = -1
30

31
        for i in range(len(edges)):
32

33
            # check if the end node is reachable from both starting nodes
34
            if n1[i] != -1 and n2[i] != -1:
35
                maximum_distance = max(n1[i], n2[i])
36

37
                # update the distance and the final answer if relevant
38
                if maximum_distance < res:
39
                    res = maximum_distance
40
                    answer = i
41

42
        return answer