LeetCode Entry

2359. Find Closest Node to Given Two Nodes

25.01.2023 medium 2023 kotlin

fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {

2359. Find Closest Node to Given Two Nodes medium

https://t.me/leetcode_daily_unstoppable/97

blog post

    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val distances = mutableMapOf<Int, Int>()
        var n = node1
        var dist = 0
        while (n != -1) {
            if (distances.contains(n)) break
            distances[n] = dist
            n = edges[n]
            dist++
        }
        n = node2
        dist = 0
        var min = Int.MAX_VALUE
        var res = -1
        while (n != -1) {
            if (distances.contains(n)) {
                val one = distances[n]!!
                val max = maxOf(one, dist)
                if (max < min || max == min && n < res) {
                    min = max
                    res = n
                }
            }
            val tmp = edges[n]
            edges[n] = -1
            n = tmp
            dist++
        }
        return res
    }

We can walk with DFS and remember all distances, then compare them and choose those with minimum of maximums.

• we can use visited set, or modify an input
• corner case: don’t forget to also store starting nodes

Space: O(n), Time: O(n)