## Similar Problems

Similar Problems not available

# Keys And Rooms - Leetcode Solution

## Companies:

LeetCode: Keys And Rooms Leetcode Solution

Difficulty: Medium

Topics: graph depth-first-search breadth-first-search

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).

## Keys And Rooms Solution Code

`1`