Keys and Rooms — Day 100 (Python)

Photo by Darío Martínez-Batlle on Unsplash

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

There are 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 v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
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.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

1. 1 <= rooms.length <= 1000
2. 0 <= rooms[i].length <= 1000
3. The number of keys in all rooms combined is at most 3000.

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.

class CanVisitAllRoomFinder:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        key_queue = []
        visited = [False] * len(rooms)
        for keys in rooms[0]:
            key_queue.append(keys)
        visited[0] = True
        while(key_queue):
            out = key_queue.pop(0)
            if visited[out] != True:
                for keys in rooms[out]:
                    key_queue.append(keys)
                visited[out] = True
        return True if all(visited) else False

Complexity analysis.

Time Complexity

The time complexity for this algorithm is O(N + K), where N is the number of rooms and K is the number of Keys.

Space Complexity

The space complexity is O(N) since we are using a list to store the visited rooms list.