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
PreviewRecognizing 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize 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`…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To recursively visit all rooms reachable from the current room by following keys, marking each newly discovered room as visited.
Verify All Rooms Visited After DFS Completion
To determine if the traversal covered all rooms by comparing the visited set size to the total number of rooms.
2 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why is it necessary to track visited rooms during DFS traversal?
See the answer with Pro.
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