Watch 10 video solutions for Keys and Rooms, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by Nick White has 22,079 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Example 1:
Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
Constraints:
n == rooms.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < nrooms[i] are unique.Problem Overview: You start in room 0. Each room may contain keys that unlock other rooms. The task is to determine whether you can visit every room by collecting and using these keys. Conceptually, each room is a node in a graph and each key represents a directed edge to another room.
Approach 1: Depth-First Search (DFS) (Time: O(n + e), Space: O(n))
Treat the input as a graph where room i has edges to the rooms listed in rooms[i]. Start a DFS from room 0. Every time you enter a room, mark it as visited and recursively explore all rooms whose keys you find there. A visited set or boolean array prevents revisiting rooms and avoids infinite cycles. After traversal finishes, check whether the number of visited rooms equals n. This approach works well because DFS naturally follows chains of keys deep into the graph before backtracking.
The key insight: the problem is simply checking whether all nodes are reachable from node 0. DFS efficiently explores reachability in graphs while maintaining O(n + e) time where n is the number of rooms and e is the total number of keys.
DFS is commonly used in graph traversal problems, especially when exploring connected components or reachability. If you want to review the concept, see Depth-First Search and Graph.
Approach 2: Breadth-First Search (BFS) (Time: O(n + e), Space: O(n))
BFS solves the same reachability problem but explores rooms level by level. Use a queue starting with room 0. Dequeue a room, mark it visited, and enqueue every new room whose key appears inside it. Each room is processed once, and each key is examined once, giving O(n + e) time complexity.
The difference from DFS is traversal order. BFS spreads outward from the starting room rather than diving deep first. In practice both approaches perform similarly for this problem. BFS may feel more intuitive if you think of unlocking rooms layer by layer.
BFS is another core traversal technique in graph problems. See Breadth-First Search for a deeper explanation.
Recommended for interviews: Either DFS or BFS is acceptable since both achieve optimal O(n + e) time and O(n) space. DFS is often slightly shorter to implement with recursion, while BFS demonstrates comfort with queue-based graph traversal. Interviewers mainly look for the recognition that rooms and keys form a graph reachability problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(n + e) | O(n) | Great for recursive exploration of graph reachability and concise implementations. |
| Breadth-First Search (BFS) | O(n + e) | O(n) | Useful when exploring nodes level-by-level using a queue. |