841. Keys and Rooms

841. Keys and Rooms

Problem Solving - Day 80

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


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!