Problem Explanation

Each room in the problem is represented as a list of keys, and each room is an index in a parent list, allowing us to treat the keys as a graph where rooms are nodes and keys are edges. The solution to this problem will involve using depth-first search (DFS) to traverse all connected rooms, marking each visited room. If all rooms have been visited, we return True. If not, we return False.

Let's consider an example.

Consider a list of rooms where there are four rooms 0, 1, 2 and 3:

1
2
3 Rooms: [[1],[2],[3],[]]

Here, each inner list represents the keys in a room. Room 0 has key 1, Room 1 has key 2, and Room 2 has key 3. Room 3 does not contain any keys.

All rooms start locked except Room 0. In Room 0, we pick up key 1 which opens door 1. Inside Room 1, we get key 2 which opens Room 2. In Room 2, we find the key 3 which opens Room 3. Thus, we can enter every room and hence return true.

Solution Approach

The solution uses Depth First Search (DFS). Starting from room 0, we try to reach every other room. If we can reach a room, we pick up the keys in that room and try to unlock additional rooms. We keep track of the rooms we have already visited. At the end, if we have visited all rooms, we return True, otherwise, we return False.

Detailed Steps

• Start from Room 0 and add it to stack and mark it as visited.

• Iterate till stack is not empty:

  • pop the last one as the current room.

  • Add childs of the current node into stack only if they are not visited before.

• In the end, check if all rooms were visited.

• If all rooms were visited, return True otherwise return False.

We can illustrate these steps with above example

Step 1

Stack: [0] Visited: [True, False, False, False]

Step 2

Stack: [1] Visited: [True, True, False, False]

Step 3

Stack: [2] Visited: [True, True, True, False]

Step 4

Stack: [3] Visited: [True, True, True, True]

Step 5

We have visited all rooms, hence return True.

Now, let's implement it in different languages.

Python Solution

1
2python
3class Solution:
4    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
5        stack = [0]  # start from room 0
6        visited = {0}
7        while stack:
8            room = stack.pop()  # get the current room
9            for key in rooms[room]:  # get all keys in this room
10                if key not in visited:  # if the room is not visited, add it to the stack
11                    visited.add(key)
12                    stack.append(key)
13        return len(visited) == len(rooms)  # if all rooms are visited, return True

Java Solution

1
2java
3class Solution {
4    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
5        boolean[] seen = new boolean[rooms.size()];
6        Stack<Integer> stack = new Stack<>();
7        stack.push(0);
8        seen[0] = true;
9        while (!stack.isEmpty()) {
10            int room = stack.pop();
11            for (int key : rooms.get(room)) {
12                if (!seen[key]) {
13                    seen[key] = true;
14                    stack.push(key);
15                }
16            }
17        }
18        for (boolean visited : seen) {
19            if (!visited) return false;
20        }
21        return true;
22    }
23}

Javascript Solution

1
2javascript
3var canVisitAllRooms = function(rooms) {
4    let visited = new Array(rooms.length).fill(false);
5    visited[0] = true;
6    let stack = [0];
7    while (stack.length > 0) {
8        let room = stack.pop();
9        for (let key of rooms[room]) {
10            if (!visited[key]) {
11                visited[key] = true;
12                stack.push(key);
13            }
14        }
15    }
16    return visited.every(v => v === true);
17};

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool canVisitAllRooms(vector<vector<int>>& rooms) {
6        vector<bool> seen(rooms.size(), false);
7        seen[0] = true;
8        stack<int> keys;
9        keys.push(0);
10        while (!keys.empty()) {
11            int curr_key = keys.top();
12            keys.pop();
13            for (auto& key : rooms[curr_key]) {
14                if (!seen[key]) {
15                    seen[key] = true;
16                    keys.push(key);
17                }
18            }
19        }
20        return all_of(seen.begin(), seen.end(), [](bool v) { return v; });
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
5        bool[] seen = new bool[rooms.Count];
6        Stack<int> stack = new Stack<int>();
7        stack.Push(0);
8        seen[0] = true;
9        while(stack.Count > 0) {
10            int room = stack.Pop();
11            foreach(int key in rooms[room]) {
12                if (!seen[key]) {
13                    seen[key] = true;
14                    stack.Push(key);
15                }
16            }
17        }
18        foreach(bool visit in seen) {
19            if (!visit) return false;
20        }
21        return true;
22    }
23}

Python Solution Explained

In our Python solution, we define a class Solution with a method canVisitAllRooms that takes a list of rooms as input.

We start the program by initializing the stack with room 0 and marking it as visited. We initiate a while loop that continues as long as there are items in the stack. At each iteration, we remove the last room from the stack and for each key in that room, we check if it leads to an unvisited room. If it does, we add the room to the visited set and also to the stack to repeat the process and visit all rooms accessible from that room.

Finally, we return a boolean indicating whether the size of the visited set matches the total number of rooms or not. If this is the case, it means that all rooms have been visited and hence, we return True. If not all rooms were visited, we return False.

Java Solution Explained

The Java solution also captures this logic, but with a few differences due to the language syntax. Instead of a set, we use a boolean array seen to keep track of the visited rooms. Room indices are the indices of the array and the values are set to true if the room has been visited and false otherwise.

We then use a stack to hold the keys from each room. A while loop iterates over the stack, processing each room, marking it as visited and adding the keys found in each room to the stack.

At the end, a for-each loop runs over the size of visited array to check if all the rooms are visited. If any of the rooms were not visited, it returns False immediately. If no unvisited rooms are found, it finally returns True, indicating all rooms were visited.

Javascript Solution Explained

The Javascript solution follows the same DFS logic, initializing an array to mark visited rooms, and a stack to manage the rooms to visit. It starts from room 0, mark it as visited, and then add it to the stack. It then enters a while loop and continue to visit rooms until the stack is empty. It traverses through the graph by popping a node from the stack and visiting the unvisited rooms (children).

Finally, it uses the every method to check if every room has been visited. The every function returns true if all rooms are true (visited), and false if any room is false (not visited).

Overall, all of these solutions make use of the depth-first search algorithm to traverse through the rooms and mark each visited room. They then test to see if all rooms have been visited and return the result. Each solution accomplishes this in a slightly different manner, depending on the specific features and syntax of each language.