Algorithm
Problem Name: 841. Keys and Rooms
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.
Example 2:
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.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < n- All the values of
rooms[i]are unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
// DFS
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int count = 0, n = rooms.size();
vector<int>visited(n);
dfs(rooms, 0, visited, count);
return count == n;
}
void dfs(vector < vector<int>>& rooms, int pos, vector<int>& visited, int& count){
if(visited[pos]) return;
count++;
visited[pos] = 1;
for(auto x: rooms[pos]) dfs(rooms, x, visited, count);
}
};
// BFS
class Solution {
public:
bool canVisitAllRooms(vector<vector < int>>& rooms) {
int count = 0, n = rooms.size();
vector<int>visited(n>;
queue < int>q;
q.push(0);
while(!q.empty()){
int x = q.front();
q.pop();
if(visited[x]) continue;
visited[x] = 1;
count++;
for(auto neigh: rooms[x]) q.push(neigh);
}
return count == n;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean canVisitAllRooms(List visited = new HashSet<>();
Queue queue = new LinkedList<>();
queue.add(0);
visited.add(0);
while (!queue.isEmpty()) {
int removed = queue.remove();
for (Integer nextRoom : rooms.get(removed)) {
if (!visited.contains(nextRoom)) {
queue.add(nextRoom);
visited.add(nextRoom);
}
}
}
return visited.size() == rooms.size();
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const canVisitAllRooms = function(rooms) {
const stack = [];
const seen = [];
for (let i = 0; i < rooms.length; i++) {
seen[i] = false;
}
seen[0] = true;
stack.push(0);
while (stack.length) {
let node = stack.pop();
for (let el of rooms[node]) {
if (!seen[el]) {
seen[el] = true;
stack.push(el);
}
}
}
for (let el of seen) {
if (!el) return false;
}
return true;
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def canVisitAllRooms(self, rooms):
pool, stack = set(range(len(rooms))), [0]
while stack:
pool.discard(stack[-1])
for nex in rooms[stack.pop()]:
if nex in pool:
stack.append(nex)
return not pool
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0841_KeysAndRooms
{
public bool CanVisitAllRooms(IList < IList<int>> rooms)
{
var seen = new HashSet < int>();
seen.Add(0);
var queue = new Queue < int>();
queue.Enqueue(0);
while (queue.Count > 0)
{
var roomId = queue.Dequeue();
foreach (var key in rooms[roomId])
{
if (!seen.Contains(key))
{
seen.Add(key);
queue.Enqueue(key);
}
}
}
return seen.Count == rooms.Count;
}
}
}
Input
Output