Problem
There are n rooms labeled from0 to n - 1. All rooms are locked except room 0. Each room contains a list of keys that can be used to unlock other rooms.
Return
true if it is possible to visit every room. Otherwise, return false.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
rooms = [[1],[2],[3],[]]Output
trueExample 2
Input
rooms = [[1,3],[3,0,1],[2],[0]]Output
falseSolution
Solution 1: DFS
This solution uses Depth-First Search (DFS). We start from room0 and use every key found in a visited room to recursively explore other rooms.
A visited array keeps track of the rooms that have already been visited, preventing the same room from being processed multiple times. After the DFS traversal, if every room has been visited, we return
true.
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] visited = new boolean[rooms.size()];
dfs(0, rooms, visited);
for (boolean room : visited) {
if (!room) {
return false;
}
}
return true;
}
private void dfs(int room, List<List<Integer>> rooms, boolean[] visited) {
if (visited[room]) {
return;
}
visited[room] = true;
for (int key : rooms.get(room)) {
dfs(key, rooms, visited);
}
}
}Solution 2: BFS
This solution uses Breadth-First Search (BFS) with a Queue. We start with room0 in the queue and process each room to collect the keys available inside it.
A HashSet keeps track of visited rooms. Whenever we visit a room, all keys found inside it are added to the queue. At the end, if the number of visited rooms equals the total number of rooms, every room is reachable.
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> keys = new LinkedList<>();
keys.offer(0);
while (!keys.isEmpty()) {
int key = keys.poll();
if (!visited.contains(key)) {
visited.add(key);
keys.addAll(rooms.get(key));
}
}
return visited.size() == rooms.size();
}
}Complexity
Both solutions visit every room and process every key at most once, so the time complexity isO(n + k), where n is the number of rooms and k is the total number of keys.
Both solutions use
O(n) extra space for tracking visited rooms. DFS additionally uses recursion stack space, while BFS uses a queue.