LeetCode Entry

1971. Find if Path Exists in Graph

19.12.2022 easy 2022 kotlin

fun validPath(n: Int, edges: Array, source: Int, destination: Int): Boolean {

1971. Find if Path Exists in Graph easy

https://t.me/leetcode_daily_unstoppable/57

blog post

    fun validPath(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
        if (source == destination) return true
        val graph = mutableMapOf<Int, MutableList<Int>>()
        edges.forEach { (from, to) ->
            graph.getOrPut(from, { mutableListOf() }).add(to)
            graph.getOrPut(to, { mutableListOf() }).add(from)
        }
        val visited = mutableSetOf<Int>()
        with(ArrayDeque<Int>()) {
            add(source)
            var depth = 0
            while(isNotEmpty() && ++depth < n) {
                repeat(size) {
                    graph[poll()]?.forEach {
                        if (it == destination) return true
                        if (visited.add(it)) add(it)
                    }
                }
            }
        }
        return false
    }

BFS will do the job. Make node to nodes map, keep visited set and use queue for BFS.

• also path can’t be longer than n elements

Space: O(N), Time: O(N)