Hello, reader ππ½ ! Welcome to day 80 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.
Today, I will be picking up LeetCode's daily challenge problem: 841. Keys and Rooms.
π€ Problem Statement
There are
n
rooms labelled from0
ton - 1
and all the rooms are locked except for room0
.The goal is to visit all the rooms. However, a locked room cannot be entered without having its key.
Each room has a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and all of them can be used to unlock the other rooms.
Given an array
rooms
whererooms[i]
is the set of keys that can be obtained if roomi
was visited, returntrue
if all the rooms can be visited, orfalse
otherwise.E.g.:
rooms = [[1],[2],[3],[]] => true rooms = [[1,3],[3,0,1],[2],[0]] => false
π¬ Thought Process - BFS
In this problem, we are directly given the adjacence list containing nodes and all of their neighbours.
Note that the nodes here are the rooms and the edges are the given keys.
The question boils down to whether or not all the nodes have been visited.
To solve this, a normal BFS/ DFS traversal can be done with a visited set/ array that keeps track of all the nodes that have been seen already.
After the traversal, if the set has a size of
n
, then it means that every node has been visited at least once. That is, we have visited all the rooms.- If you are using a boolean array of size
n
, then you should check ifboolean[i]
for all indices from0
ton
are true.
- If you are using a boolean array of size
But after the traversal, if the size of the set is not
n
, then all the nodes were not visited, we returnfalse
.
π©π½βπ» Solution - BFS
- Below is the code for the approach for solving this problem using a BFS traversal.
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
Set<Integer> visitedRooms = new HashSet();
Queue<Integer> roomsToBeProcessed = new LinkedList();
// start traversing from room 0
roomsToBeProcessed.add(0);
visitedRooms.add(0);
while(!roomsToBeProcessed.isEmpty()) {
int currRoom = roomsToBeProcessed.poll();
for(int nextRoom: rooms.get(currRoom)) {
if(!visitedRooms.contains(nextRoom)) {
visitedRooms.add(nextRoom);
roomsToBeProcessed.add(nextRoom);
}
}
}
return (visitedRooms.size() == n);
}
}
Time Complexity: O(v + e)
- e = number of keys
- v = number of rooms
Space Complexity: O(v + e)
- e = number of keys
- v = number of rooms
π¬ Thought Process - DFS
The problem can also be solved using the DFS traversal approach were we visit all the rooms simultaneously.
We can use a similar visited set that marks and holds all the visited nodes.
- But to demonstrate the use of maintaining a visited array, I will be using a visited array of type boolean and size
n
for the code below.
- But to demonstrate the use of maintaining a visited array, I will be using a visited array of type boolean and size
π©π½βπ» Solution - DFS
- Below is the code for the approach for solving this problem using a DFS traversal.
class Solution {
private int n;
private boolean[] visitedRooms;
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
n = rooms.size();
visitedRooms = new boolean[n];
traverseRooms(rooms, 0);
for(boolean isVisited: visitedRooms) {
if(!isVisited) return false;
}
return true;
}
private void traverseRooms(List<List<Integer>> rooms, int room) {
visitedRooms[room] = true;
for(int nextRoom: rooms.get(room)) {
if(!visitedRooms[nextRoom]) {
traverseRooms(rooms, nextRoom);
}
}
}
}
Time Complexity: O(v + e)
- e = number of keys
- v = number of rooms
Space Complexity: O(v + e)
- e = number of keys
- v = number of rooms
- You can find the link to the GitHub repo for this question here: 841. Keys and Rooms.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!