841.keys-and-rooms.md

841. Keys and Rooms

Clarification Questions

• Does the input list of rooms contain duplicate keys?

Test Cases

Normal Cases

• All rooms are visited.
• Not all rooms are visited.

Edge / Corner Cases

• There are keys to all rooms except the first room.

Travesal

We can use either DFS or BFS to traverse to get the keys from room 0, and then try to visit all the rooms.

• Start from room 0 and keep track of the visited rooms.
• Get the keys from the current room and visit the rooms the keys can open.
• Iterate the visited rooms to see if all rooms are visited.

fun canVisitAllRooms(rooms: List<List<Int>>): Boolean {
    val n = rooms.size
    val visited = HashSet<Int>()
    // dfs(rooms, 0, visited)
    bfs(rooms, visited)
    for (i in 0 until n) {
        if (!visited.contains(i)) return false
    }
    return true
}

// Time complexity: O(n + e)
// Space complexity: O(n): visited and recursive call stack, as the recursion goes as deep as the number of roooms.
private fun dfs(rooms: List<List<Int>>, i: Int, visited: HashSet<Int>) {
    if (visited.contains(i)) return
    visited.add(i)

    rooms[i].forEach { adj ->
        dfs(rooms, adj, visited)
    }
}

// Time complexity: O(n + e)
// Space complexity: O(n): visited
private fun bfs(rooms: List<List<Int>>, visited: HashSet<Int>) {
    val queue = ArrayDeque<Int>()
    queue.addLast(0)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()

        if (visited.contains(node)) continue
        visited.add(node)

        rooms[node].forEach { adj -> 
            queue.addLast(adj)
        }
    }
}

private fun bfs(rooms: List<List<Int>>, visited: HashSet<Int>) {
    val queue = ArrayDeque<Int>()
    queue.addLast(0)
    visited.add(0)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        for (adj in rooms[node]) {
            if (adj in visited) continue
            queue.addLast(adj)
            visited.add(adj)
        }
    }
}

• Time Complexity: O(n + e), where n is the number of rooms and e is the number of keys.
• Space Complexity: O(n), where n is the number of rooms.