841. Keys and Rooms

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 from 0 to n - 1 and all the rooms are locked except for room 0.
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 where rooms[i] is the set of keys that can be obtained if room i was visited, return true if all the rooms can be visited, or false 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 if boolean[i] for all indices from 0 to n are true.
But after the traversal, if the size of the set is not n, then all the nodes were not visited, we return false.

👩🏽‍💻 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.

👩🏽‍💻 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!

Bharati Subramanian