Keys And Rooms - Leetcode Solution

Problem Statement:

You are given an array called rooms which consists of n different rooms, numbered from 0 to n-1. Each room contains a set of keys that are needed to access other rooms. The key set in room i is represented as a list of integers rooms[i], which consists of unique integers in the range [0, n-1]. A key key in rooms[i] allows you to open a door to room key.

You start from room 0 and must visit every room. You can use any keys that are currently in your possession, but you cannot enter a room that you do not have a key for. If you can visit every room, return True, otherwise return False.

Solution:

To solve this problem, we can use a Depth First Search (DFS) algorithm to explore all the rooms. We can start by visiting room 0 and adding all its keys to a set called visited. We can then iterate through the keys of room 0 and recursively visit all the rooms that have not been visited yet, adding their keys to the set as we go along. We can repeat this process until we have visited all the rooms or until we cannot visit any more rooms.

To keep track of which rooms we have visited, we can use a boolean array called visited_rooms where visited_rooms[i] is True if we have visited room i and False otherwise. Initially, all elements of visited_rooms are False. Whenever we visit a new room, we mark its corresponding element in visited_rooms to be True.

Once we have visited all the rooms, we can check if all elements of visited_rooms are True. If they are, we return True, otherwise we return False.

Algorithm:

1. Create a boolean array called visited_rooms of size n and set all its elements to False.
2. Create a set called visited and add 0 to it.
3. Call the DFS function with inputs rooms, 0, visited, and visited_rooms.
4. In the DFS function, iterate through the keys of room u and if the corresponding element in visited_rooms is False, recursively call the DFS function with inputs rooms, key, visited, and visited_rooms.
5. Mark the corresponding element in visited_rooms to be True.
6. Return from the DFS function.
7. Check if all elements of visited_rooms are True. If they are, return True, otherwise return False.

Implementation:

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited_rooms = [False] * n
        visited = set()
        visited.add(0)
        
        def dfs(u):
            for key in rooms[u]:
                if not visited_rooms[key]:
                    visited.add(key)
                    dfs(key)
            visited_rooms[u] = True
        
        dfs(0)
        return all(visited_rooms)

Time Complexity:

The time complexity of this algorithm is O(n + m) where n is the number of rooms and m is the total number of keys in all the rooms. This is because we visit each room only once and we iterate through all the keys in all the rooms. Since m can be at most equal to n^2, the time complexity of this algorithm is O(n^2) in the worst case.

Space Complexity:

The space complexity of this algorithm is O(n) because we use a boolean array called visited_rooms of size n to keep track of which rooms we have visited. We also use a set called visited for the same purpose, which can contain at most n elements. In addition, we use the recursive stack of the DFS function, which can contain at most n elements. Therefore, the total space complexity of this algorithm is O(n).

1