Keys and Rooms
Problem
Given a list of rooms where each room contains a list of keys to other rooms, return true if all rooms can be visited starting from room 0, otherwise return false.
- 1 ≤ rooms.length ≤ 1000
- 0 ≤ rooms[i].length ≤ 1000
- The keys in rooms[i] are integers in the range [0, rooms.length - 1]
Example
rooms = [[1],[2],[3],[]]trueStarting from room 0, the keys available are [1]. Visit room 1, which contains key [2]. Visit room 2, which contains key [3]. Visit room 3, which contains no keys. All rooms (0 to 3) have been visited, so the output is true.
Approach
Straightforward Solution
A brute-force approach would attempt to visit rooms arbitrarily or repeatedly check reachability, potentially revisiting rooms multiple times, leading to inefficient exploration.
Core Observation
The problem reduces to checking if all nodes (rooms) in a directed graph are reachable from a starting node (room 0). Each room is a node, and keys represent directed edges to other nodes.
Path to Optimal
Recognizing the problem as a graph traversal task, Depth-First Search (DFS) or Breadth-First Search (BFS) can systematically explore all reachable rooms from room 0. DFS is chosen here for its simplicity and natural recursive structure. By tracking visited rooms in a set, the algorithm avoids revisiting rooms and ensures linear time complexity relative to the total number of keys.
Optimal Approach
Initialize a set `seen` with room 0 to mark it as visited. Define a recursive DFS function that, for each room, iterates over its keys and recursively visits any unvisited rooms, adding them to `seen`. After the DFS completes, compare the size of `seen` to the total number of rooms. If all rooms are visited, return true; otherwise, false.
Time
O(N + E)
Each room (node) is visited once, and each key (edge) is explored once during DFS, resulting in linear time relative to the number of rooms plus total keys.
Space
O(N)
The `seen` set stores visited rooms, which can grow up to the total number of rooms N. The recursion stack can also grow up to O(N) in the worst case.
Pattern Spotlight
DFS (Graph Reachability)
When determining if all nodes in a graph are reachable from a starting node, use DFS to explore all connected nodes recursively, marking visited nodes to avoid cycles and redundant work.
Solution
| 1 | class Solution:
|
| 2 | def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
|
| 3 | def dfs(node):
|
| 4 | for neighbor in rooms[node]:
|
| 5 | if neighbor not in seen:
|
| 6 | seen.add(neighbor)
|
| 7 | dfs(neighbor)
|
| 8 |
|
| 9 | seen = {0}
|
| 10 | dfs(0)
|
| 11 | return len(seen) == len(rooms) |
Step-by-Step Solution
Mark Starting Room as Visited and Begin DFS
| 9 | seen = {0}
|
| 10 | dfs(0)
|
Objective
To initialize the visited set with the starting room and begin recursive exploration from room 0.
Key Insight
Starting with room 0 marked as visited ensures the DFS begins from the correct node and that the algorithm does not revisit the starting room unnecessarily. This setup is critical to correctly track which rooms have been accessed during traversal.
Interview Quick-Check
Core Logic
Initializing the visited set with room 0 ensures the DFS starts from the correct node and prevents revisiting it.
State & Boundaries
The visited set acts as a boundary to prevent infinite recursion and redundant visits.
Recursively Explore All Reachable Rooms via DFS
| 3 | def dfs(node):
|
| 4 | for neighbor in rooms[node]:
|
| 5 | if neighbor not in seen:
|
| 6 | seen.add(neighbor)
|
| 7 | dfs(neighbor)
|
Objective
To recursively visit all rooms reachable from the current room by following keys, marking each newly discovered room as visited.
Key Insight
The recursive DFS explores each neighbor (key) of the current room. By checking if a neighbor has not been visited before recursing, the algorithm avoids cycles and redundant work. This ensures a complete and efficient traversal of all reachable rooms.
Interview Quick-Check
Core Logic
DFS recursively explores neighbors only if they have not been visited, ensuring each room is visited exactly once.
Common Pitfalls & Bugs
Failing to check if a neighbor is already visited before recursion can cause infinite loops or stack overflow.
State & Boundaries
The recursion terminates naturally when all reachable rooms have been visited.
Verify All Rooms Visited After DFS Completion
| 11 | return len(seen) == len(rooms) |
Objective
To determine if the traversal covered all rooms by comparing the visited set size to the total number of rooms.
Key Insight
If the number of visited rooms equals the total number of rooms, it means all rooms are reachable from room 0. This final check converts the traversal result into the problem's required boolean output.
Interview Quick-Check
Core Logic
Comparing the size of the visited set to the total number of rooms confirms whether all rooms are reachable.
State & Boundaries
Returning the boolean result immediately after DFS ensures no unnecessary computation.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if neighbor not in seen:Check if the neighbor room has not been visited yet.
This condition prevents revisiting rooms, which avoids infinite recursion and redundant work, ensuring correctness and efficiency.
return len(seen) == len(rooms)Return true if all rooms have been visited, false otherwise.
Comparing the size of the visited set to the total number of rooms provides a definitive answer to whether all rooms are reachable.
seen.add(neighbor)Mark the neighbor room as visited.
Adding the neighbor to the visited set immediately upon discovery prevents duplicate visits and cycles during recursion.
dfs(neighbor)Recursively call DFS on the neighbor room.
This recursive call explores all rooms reachable from the neighbor, enabling a full traversal of the graph starting from room 0.
seen = {0}Initialize the visited set with room 0 as the starting point.
Starting with room 0 marked as visited ensures the traversal begins correctly and prevents revisiting the starting room.
dfs(0)Invoke DFS starting from room 0.
This call triggers the recursive exploration of all reachable rooms from the starting point.
def dfs(node):Define the recursive DFS function to explore reachable rooms from a given node.
Encapsulating the traversal logic in a recursive function allows systematic exploration of all neighbors, enabling a clean and natural graph traversal.
for neighbor in rooms[node]:Iterate over all keys (neighbors) in the current room.
Visiting each neighbor is essential to explore all possible paths and discover all reachable rooms.
Test Your Understanding
Why is it necessary to track visited rooms during DFS traversal?
Tracking visited rooms prevents infinite recursion caused by cycles and avoids redundant exploration, ensuring each room is processed only once for efficiency and correctness.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Keys and Rooms from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Keys and Rooms drill