Keys and Rooms — Day 100 (Python)
Today’s question is from Daily Leetcode Coding Challenge — March Edition. It is a medium-tagged question. Let us look into the problem statement.
841. Keys and Rooms
N rooms and you start in room
0. Each room has a distinct number in
0, 1, 2, ..., N-1, and each room may have some keys to access the next room.
Formally, each room
i has a list of keys
rooms[i], and each key
rooms[i][j] is an integer in
[0, 1, ..., N-1] where
N = rooms.length. A key
rooms[i][j] = v opens the room with number
Initially, all the rooms start locked (except for room
You can walk back and forth between rooms freely.
true if and only if you can enter every room.
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3. Since we were able to go to every room, we return true.
Explanation: We can't enter the room with number 2.
1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
- The number of keys in all rooms combined is at most
We have a list of rooms. Each index in the list represents room numbers. Within each room, we have few keys. Except for room 0, we would require keys to enter any other room. We start from room 0, collect the keys present in room 0. Let us keep all the keys that we collect in a queue. We visit the next rooms by taking keys present in our queue. Each time we visit a new room, let us keep all the keys present in this room in the queue.
What about edge cases when Room 1 has the key for Room 2 and Room 2 has the key for Room 1. In such a case, we will have a circular relation. To avoid circular relations, we can make use of a visited list that is of the same size as the number of rooms. The visited list is initialized as False.
This reminds us of BFS algorithm. Let us use BFS to solve this problem.
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
key_queue = 
visited = [False] * len(rooms)
for keys in rooms:
visited = True
out = key_queue.pop(0)
if visited[out] != True:
for keys in rooms[out]:
visited[out] = True
return True if all(visited) else False
The time complexity for this algorithm is O(N + K), where N is the number of rooms and K is the number of Keys.
The space complexity is O(N) since we are using a list to store the visited rooms list.