In this guide, you will get 841. Keys and Rooms LeetCode Solution with the best time and space complexity. The solution to Keys and Rooms problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There are n rooms labeled from 0 to n – 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Example 1:
Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.
Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
Constraints:
n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
All the values of rooms[i] are unique.
Complexity Analysis
Time Complexity: O(|V| + |E|)
Space Complexity: O(|V|)
841. Keys and Rooms LeetCode Solution in C++
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
vector<bool> seen(rooms.size());
dfs(rooms, 0, seen);
return ranges::all_of(seen, [](int s) { return s == true; });
}
private:
void dfs(const vector<vector<int>>& rooms, int node, vector<bool>& seen) {
seen[node] = true;
for (const int child : rooms[node])
if (!seen[child])
dfs(rooms, child, seen);
}
}; /* code provided by PROGIEZ */
841. Keys and Rooms LeetCode Solution in Java
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int[] seen = new int[rooms.size()];
dfs(rooms, 0, seen);
return Arrays.stream(seen).allMatch(a -> a == 1);
}
private void dfs(List<List<Integer>> rooms, int node, int[] seen) {
seen[node] = 1;
for (final int child : rooms.get(node))
if (seen[child] == 0)
dfs(rooms, child, seen);
}
} // code provided by PROGIEZ
841. Keys and Rooms LeetCode Solution in Python
class Solution:
def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
seen = [False] * len(rooms)
def dfs(node: int) -> None:
seen[node] = True
for child in rooms[node]:
if not seen[child]:
dfs(child)
dfs(0)
return all(seen) # code by PROGIEZ
