Keys and Rooms: Detailed Javascript Solution Using Queues.
I have recently been solving LeetCode problems to get more comfortable with data structures. Knowing which data structure to use for a particular problem comes with practice. Therefore, I think that a good way to understand queues better is to look at the solution to the Keys and Rooms LeetCode problem. Before we do that, let’s review what a queue is.
The queue data structure follows the same concept as a real-life queue. Imagine a queue of people in a coffee shop for example, the person who gets served first would be the person who arrived on the queue first, save for someone skipping ahead in line. We can represent this in Javascript using arrays. If an array of items is our queue, then to dequeue items, we would need to start from the first item in the queue.
For example, in the array [a,b,c,d,e] the first item to be dequeued would be a. We can perform this dequeuing using the inbuilt array.shift() method.
Now, let’s take a look at the LeetCode Keys and Rooms Question:
There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, …, N-1, and each room may have some keys to access the next room.
Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, …, N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.
Initially, all the rooms start locked (except for room 0).
You can walk back and forth between rooms freely.
Return true if and only if you can enter every room.
The input to the solution function would be an array of arrays where each array represents a room and the values in the array represent keys. So the input [[1], [3], [2]] would mean that there are 2 rooms (counting from index 0). In the zeroth room, we find the key for room one so we can unlock room one. After unlocking room one, we find the key for room 3 in room one. The next room after one is 2, so since we don’t have key 2 yet, we cannot enter room 2. Therefore if given this input, our function should return false.
Let’s try to figure out the solution using another example. Assuming we have the input [[1,3],[2,0,1],[0,3],[0]]. We need to visit each room sequentially and keep track of the key(s) that we have. How do we do this? We can queue each array (visit each room) and then sequentially dequeue each array, loop through the array and store all the keys in that array in a separate array. If that sounds confusing, it will get clearer in a bit. First of all, we initialize our queue that “visits” each room starting from room zero.
rooms = [[1,3],[2,0,1],[0,3], [0]]
q = [];
keys = [0];
q.push(rooms[0]);keys will initially contain the key for room zero because that is where we are starting. We now have room zero in the queue.
q = [[1,3]]
Now in room zero, we have to collect the keys and store them in the keys array. To do this, we retrieve the first item (room) in q , loop through all the keys in that room and store each key (that is not already in keys) in keys.
let room = q.shift();
room.forEach(function(item){
if(!keys.includes(item)){
keys.push(item)
q.push(rooms[item])
}
})As we retrieve each key, we are also adding the room that the key opens to the queue. So following our example, q and keys will now look like this:
q = [[2,0,1], [0]];
keys = [0,1,3]If we repeat the code above, q and keys will become:
q = [[0],[0,3]];
keys = [0,1,3,2]We would need to use a while loop to repeat the code above until we run out of rooms to enter. Note that we keep taking out the first item in the queue and putting a new room in the queue only when we have not visited that room previously. So when our queue is empty, we have run out of rooms to enter and we need to exit out of the while loop.
while(q.length > 0){
let room = q.shift();
room.forEach(function(item){
if(!keys.includes(item)){
keys.push(item)
q.push(rooms[item])
}
})
}When we have exited the while loop, if we were able to visit all the rooms, we should have all the keys stored in keys. So we can use a for loop to check if the key to each room is contained in keys.
The complete solution will look something like this:
var canVisitAllRooms = function(rooms) {
let q = [];
q.push(rooms[0])
let keys = [0]
while(q.length > 0){
let room = q.shift();
room.forEach(function(item){
if(!keys.includes(item)){
keys.push(item)
q.push(rooms[item])
}
})
}
for(let i = 1; i<rooms.length; i++){
if(!keys.includes(i)){
return false
}
}
return true;};
