Leetcode 2359. Find Closest Node to Given Two Nodes - kotlin

 

 

https://leetcode.com/problems/find-closest-node-to-given-two-nodes/

Find Closest Node to Given Two Nodes - LeetCode

 

class Solution {
    val visited = BooleanArray(100001){false}
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val d1 = IntArray(100001){-1}
        val d2 = IntArray(100001){-1}
        visited[node1] = true
        dfs(edges = edges, node = node1, acc = 0, storage = d1)
        visited[node1] = false
    
        visited[node2] = true
        dfs(edges = edges, node = node2, acc = 0, storage = d2)
        visited[node2] = false

        var smallest = Int.MAX_VALUE
        var ind = -1
        for (i in 0 until edges.size){
            if(d1[i] != -1 && d2[i] != -1 && smallest > Math.max(d1[i], d2[i])){
                smallest = Math.max(d1[i] ,d2[i])
                ind = i
            }   
        }
        return ind
        
    }

    fun dfs(edges: IntArray, node: Int, acc:Int, storage: IntArray) {
        if(storage[node] < acc) {
            storage[node] = acc 
            val next = edges[node]

            if(next != -1 && !visited[next]) {
                visited[next] = true
                dfs(edges = edges, node = next, acc = acc + 1, storage = storage)
                visited[next] = false
            }
        }
    }
}

this solution starts by initialzing `d1` and `d2` of size 100_001. These arrays will store the distances from the two given nodes to all other nodes which includes both in the graph.

 

the method performs dfs algorithm starting from `node1`, and for each visited node, it stores the distnace as acc to that node in `d1`. 'node2' and 'd2' is same with. 

 

After both dfs are completed, the method iterates through the `edges` array, and for each index i it checks if the distance of that node in both `d1` and `d2` is not -1. if is not -`, it cheks if the max of both distance is smaller than the previous smallest value. if it is it updates the smallest value and the index.

 

Finally, it returns the index of the node that has the smallest max distance from both `node1` and `node2`