LeetCode Entry

841. Keys and Rooms

20.12.2022 medium 2022 kotlin

fun canVisitAllRooms(rooms: List>): Boolean {

841. Keys and Rooms medium

https://t.me/leetcode_daily_unstoppable/58

blog post

    fun canVisitAllRooms(rooms: List<List<Int>>): Boolean {
       val visited = hashSetOf(0)
       with(ArrayDeque<Int>()) {
           add(0)
           while(isNotEmpty()) {
               rooms[poll()].forEach {
                   if (visited.add(it)) add(it)
               }
           }
       }
       return visited.size == rooms.size
    }

We need to visit each room, and we have positions of the other rooms and a start position. This is a DFS problem. Keep all visited rooms numbers in a hash set and check the final size. Other solution is to use boolean array and a counter of the visited rooms.

Space: O(N) - for queue and visited set, Time: O(N) - visit all the rooms once