841. Keys and Rooms
Problem Description
Imagine you're in the first room of a series of locked rooms, each with a unique label from 0
to n - 1
, where n
is the total number of rooms. Room 0
is unlocked, so you can start your exploration from there. Each room may contain a bunch of keys, and each key unlocks exactly one specific room. Your objective is to figure out if you can manage to enter every single room. The twist is, you can't waltz into a locked room without its corresponding key, which you would typically find in one of the other rooms you can access.
The question presents this scenario in the form of an array called rooms
. This array is structured so that rooms[i]
represents a list of keys that you can pick up when you enter room i
. You must determine if it's possible for you to gather all the necessary keys from the rooms you can access to ultimately open all rooms.
To solve this, you'll need to figure out a way to traverse through the rooms, beginning from the starting room (room 0
), while keeping track of the rooms you've entered and the keys you've collected along the way.
Flowchart Walkthrough
To determine the appropriate algorithm for solving LeetCode 841. Keys and Rooms, let's consult the Flowchart. Here's a step-by-step analysis:
-
Is it a graph?
- Yes: The problem represents rooms as nodes, and keys are edges between these nodes that can be traversed.
-
Is it a tree?
- No: It's not strictly a tree because a tree cannot contain cycles, but this graph may contain them if rooms have multiple keys leading to previously visited rooms.
-
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem concerns reachability and connectivity in a potentially cyclic graph rather than typical DAG operations such as topological sort.
-
Is the problem related to shortest paths?
- No: We are not required to find the shortest path; instead, the task is to determine if all rooms can be visited.
-
Does the problem involve connectivity?
- Yes: The primary goal is to verify if all nodes (rooms) can be accessed from a starting node, utilizing the given keys (edges).
Since the problem involves checking connectivity in an undirected graph and each room can be visited using keys found within the rooms themselves:
Conclusion: Based on these decisions through the flowchart, Depth-First Search (DFS) is a suitable method for solving this problem, as it efficiently explores each room's reachability from the initial room.
Intuition
To solve this puzzle, we need to think like an adventurer who's exploring a dungeon. Starting from the entrance, you go into each room, gather all the keys you find, and keep track of the rooms you've visited. Every time you find a new key, you unlock a new room and explore it for more keys.
Translating this into a solution, a Depth-First Search (DFS) approach naturally fits the problem. What we need to do is akin to exploring a graph where rooms are nodes and keys are edges connecting the nodes. We start from room 0
and try to reach all other rooms using the keys we collect.
Here's the thought process that leads to using DFS:
- Start from the initial room, which is room
0
. - If a room has been visited or a key has been used, there is no need to re-visit or re-use it.
- Traversal continues until there are no reachable rooms with new keys left.
- If at the end of the traversal, the number of visited rooms is equal to the total number of rooms, it means we've successfully visited all rooms.
- If there are still rooms left unvisited, it implies there's no way to unlock them with the keys available, hence the answer would be false.
The solution provided uses a recursive DFS function to perform this traversal, calling upon itself each time a new room is reached. The set vis
helps track visited rooms, ensuring rooms are not revisited. The return value checks if the size of vis
matches the total number of rooms.
Learn more about Depth-First Search, Breadth-First Search and Graph patterns.
Solution Approach
To implement the solution for unlocking all rooms, we use a Depth-First Search (DFS) algorithm. DFS is a common algorithm used to traverse graphs, which fits our scenario perfectly as the problem can be conceptualized as a graph where rooms are nodes and keys are the edges that connect these nodes.
Here's how the implemented DFS algorithm works step-by-step:
- We define a recursive function
dfs(u)
which accepts a room numberu
as a parameter. - The function begins by checking if the room
u
has already been visited. To efficiently check for previously visited rooms, we make use of a set calledvis
. If the current roomu
is in this set, we quit the function early since we've already been here. - If the room hasn't been visited, we add the room number
u
to the setvis
. This marks roomu
as visited and ensures we don't waste time revisiting it in future DFS calls. - Next, we iterate over all the keys found in room
u
, which are represented byrooms[u]
. - For each key
v
inrooms[u]
, we perform a recursive DFS call withv
. This is the exploration step where we are trying to dive deeper into the graph from the current node (room). - We start our DFS by calling
dfs(0)
— since room0
is where our journey begins, and it is the first room that is unlocked. - After fully exploring all reachable rooms, we check if we have visited all rooms. To do this, we compare the length of our visited set
vis
with the length of therooms
array. If they match, it means we have successfully visited every room.
The data structure used in this implementation is primarily a set (vis
). Sets in Python are collections that are unordered, changeable, and do not allow duplicate elements. The characteristics of a set make it an ideal choice to keep track of visited rooms because it provides O(1) complexity for checking the presence of an element, which is crucial for an efficient DFS implementation.
By utilizing recursion for the depth-first traversal, and a set to track the visited nodes, we apply a classical graph traversal technique to solve this problem. It's concise, efficient, and directly addresses our goal of determining whether all rooms can be visited.
By running the DFS from room 0
and continually marking each room visited and exploring the next accessible rooms through the keys, the canVisitAllRooms
function ultimately returns True
if every room has been reached, and False
if at least one room remains locked after the search is complete.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small set of rooms to illustrate the solution approach:
Suppose there are 4
rooms, and the keys are distributed as follows:
- Room
0
contains keys for rooms1
and2
. - Room
1
contains a key for room3
. - Room
2
contains no keys. - Room
3
contains no keys.
Representing this in an array, we have rooms = [[1,2], [3], [], []]
.
Using the DFS approach:
- We start the DFS with
dfs(0)
, marking room0
as visited and adding it to the setvis
. - We find two keys in room
0
, which are to rooms1
and2
, so we will traverse to these rooms next. - First, we call
dfs(1)
. Before diving into room1
, we add it to thevis
set. - Inside room
1
, we find a key to room3
. We now calldfs(3)
since room3
hasn't been visited yet. - We add room
3
to thevis
set, but find no keys in it. - With no further keys from room
3
, we backtrack to room1
, and since we've explored all its keys, we backtrack further to room0
. - Now, we call
dfs(2)
from the remaining key in room0
. - Room
2
is added to thevis
set, but since there are no keys, we have nothing further to explore from here. - We have now visited all the rooms:
vis = {0, 1, 2, 3}
. - We compare the number of visited rooms with the total number of rooms. Since both are
4
, we have successfully visited every room.
By following each key we find to the next room and keeping track of where we've been, we confirmed that it is possible to visit all the rooms. In the scenario presented by rooms
, our implementation of the canVisitAllRooms
function will return True
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
5 # Depth-first search (DFS) function that marks rooms as visited
6 def dfs(current_room):
7 # If the current room has already been visited, do nothing
8 if current_room in visited:
9 return
10 # Mark the current room as visited
11 visited.add(current_room)
12 # Perform a DFS on all the keys/rooms that are accessible from the current room
13 for key in rooms[current_room]:
14 dfs(key)
15
16 # A set to keep track of visited rooms
17 visited = set()
18 # Initiate DFS starting from room 0
19 dfs(0)
20 # If the number of visited rooms equals the total number of rooms, all rooms can be visited
21 return len(visited) == len(rooms)
22
1import java.util.List;
2import java.util.Set;
3import java.util.HashSet;
4
5class Solution {
6 private List<List<Integer>> rooms; // A list representing the keys in each room.
7 private Set<Integer> visited; // A set to track visited rooms.
8
9 // Method to check if we can visit all rooms starting from room 0.
10 public boolean canVisitAllRooms(List<List<Integer>> rooms) {
11 this.rooms = rooms; // Initialize the room list.
12 visited = new HashSet<>(); // Initialize visited set.
13 dfs(0); // Start depth-first search from room 0.
14 // If the size of visited rooms is equal to total room count, return true.
15 return visited.size() == rooms.size();
16 }
17
18 // Recursive method for depth-first search.
19 private void dfs(int roomIndex) {
20 // If the room has already been visited, return to avoid cycles.
21 if (visited.contains(roomIndex)) {
22 return;
23 }
24 // Mark the current room as visited.
25 visited.add(roomIndex);
26 // Recursively visit all rooms that can be unlocked with keys from the current room.
27 for (int nextRoomIndex : rooms.get(roomIndex)) {
28 dfs(nextRoomIndex);
29 }
30 }
31}
32
1#include <vector>
2#include <unordered_set>
3
4class Solution {
5public:
6 // Stores the list of rooms and keys within them
7 std::vector<std::vector<int>> roomKeys;
8
9 // Keeps track of visited rooms
10 std::unordered_set<int> visitedRooms;
11
12 // Returns true if all rooms can be visited using the keys in them
13 bool canVisitAllRooms(std::vector<std::vector<int>>& rooms) {
14 // Clear the visitedRooms set in case it's being reused
15 visitedRooms.clear();
16
17 // Initialize roomKeys with the input rooms and their keys
18 roomKeys = rooms;
19
20 // Start the DFS from room 0
21 dfs(0);
22
23 // If the size of visitedRooms is equal to the total number of rooms,
24 // it means we could visit all rooms
25 return visitedRooms.size() == rooms.size();
26 }
27
28 // Recursive Depth First Search function to visit rooms
29 void dfs(int currentRoom) {
30 // If we've already visited the current room, return to avoid cycles
31 if (visitedRooms.count(currentRoom)) return;
32
33 // Mark the current room as visited
34 visitedRooms.insert(currentRoom);
35
36 // Loop over every key in the current room
37 for (int key : roomKeys[currentRoom]) {
38 // Use the key to visit the next room
39 dfs(key);
40 }
41 }
42};
43
1// Define a function to determine if all rooms can be visited given a list of rooms and their keys.
2// Each room is represented by an index and contains a list of keys to other rooms.
3function canVisitAllRooms(rooms: number[][]): boolean {
4 // Determine the total number of rooms.
5 const totalRooms = rooms.length;
6
7 // Create an array to keep track of whether each room has been opened.
8 const isRoomOpen = new Array(totalRooms).fill(false);
9
10 // Initialize a stack with the key to the first room (i.e., room 0).
11 const keysStack = [0];
12
13 // Process keys while there are still keys left in the stack.
14 while (keysStack.length !== 0) {
15 // Retrieve the last key from the stack.
16 const currentKey = keysStack.pop();
17
18 // Skip processing if the room has already been opened.
19 if (isRoomOpen[currentKey]) {
20 continue;
21 }
22
23 // Mark the current room as opened.
24 isRoomOpen[currentKey] = true;
25
26 // Add all the keys found in the current room to the stack.
27 keysStack.push(...rooms[currentKey]);
28 }
29
30 // Check if all rooms have been opened. If so, return true.
31 return isRoomOpen.every(isOpen => isOpen);
32}
33
Time and Space Complexity
The time complexity of the code is O(N + E)
, where N
represents the number of rooms and E
represents the total number of keys (or edges in graph terms, representing connections between rooms). Each room and key is visited exactly once due to the depth-first search (DFS) algorithm used, and the vis
set ensures that each room is entered only once.
The space complexity of the code is also O(N)
because the vis
set can potentially contain all N
rooms at the worst-case scenario when all rooms are visited. Additionally, the recursive stack due to DFS also contributes to the space complexity, and in the worst case might store all the rooms if they are connected linearly, making the space complexity still O(N)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.