Keys and Rooms - Solution & Explanation
Problem Statement
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] < n- All the values of
rooms[i]are unique.
Approach Overview
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 1: Depth-First Search (DFS) Approach
The idea is to use Depth-First Search (DFS) to explore all reachable rooms starting from room 0. This can be implemented either recursively or iteratively with a stack. We maintain a set of visited rooms and attempt to visit all rooms that we have keys for, recursively adding rooms to the visited set as we access them. The process continues until no new rooms can be explored.
This solution defines a dfs function to explore rooms recursively. The visited set is used to keep track of rooms that have already been visited to avoid re-processing. The algorithm starts DFS from room 0, recursively visiting each room for which we have a key until no new rooms can be visited.
Complexity
Space Complexity: O(N) for the recursion stack and the visited set.
Approach 2: Breadth-First Search (BFS) Approach
Instead of using DFS, we can also use Breadth-First Search (BFS) to explore the rooms iteratively. We use a queue to maintain the rooms to be visited next. Initially, room 0 is added to the queue. As we visit each room, we add all the keys found in that room to the queue, provided we haven't visited the corresponding rooms yet. This approach ensures a layer-wise exploration similar to BFS.
In this Python BFS implementation, we utilize a deque as a queue. Initially, room 0 is added to the queue and visited set. We process each room in the queue by adding unvisited rooms (for which we have keys) to the visited set and queue. We continue this until the queue is empty and then check if all rooms have been visited.
Complexity
Space Complexity: O(N) for the queue and visited set.
Approach 3: Depth-First Search (DFS)
We can use the Depth-First Search (DFS) method to traverse the entire graph, count the number of reachable nodes, and use an array vis to mark whether the current node has been visited to prevent repeated visits.
Finally, we count the number of visited nodes. If it is the same as the total number of nodes, it means that all nodes can be visited; otherwise, there are nodes that cannot be reached.
The time complexity is O(n + m), and the space complexity is O(n), where n is the number of nodes, and m is the number of edges.
Approach 4: BFS
We can also use the Breadth-First Search (BFS) method to traverse the entire graph. We use a hash table or an array vis to mark whether the current node has been visited to prevent repeated visits.
Specifically, we define a queue q, initially put node 0 into the queue, and then continuously traverse the queue. Each time we take out the front node i of the queue, if i has been visited, we skip it directly; otherwise, we mark it as visited, and then add the nodes that i can reach to the queue.
Finally, we count the number of visited nodes. If it is the same as the total number of nodes, it means that all nodes can be visited; otherwise, it means that there are unreachable nodes.
The time complexity is O(n + m), and the space complexity is O(n). Where n is the number of nodes, and m is the number of edges.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Approach | Time Complexity: O(N + E), where N is the number of rooms and E is the total number of keys. Space Complexity: O(N) for the recursion stack and the visited set. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(N + E), where N is the number of rooms and E is the total number of keys. Space Complexity: O(N) for the queue and visited set. |
| Depth-First Search (DFS) | — |
| BFS | — |
Detailed Complexity Analysis
| 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. |
Video Solution
LeetCode Keys and Rooms Solution Explained - Java • Nick White • 22,243 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Keys and Rooms easy or hard?
Keys and Rooms Python/Java solution
How to solve Keys and Rooms in O(n)?
What is the best approach for Keys and Rooms?
Is Keys and Rooms asked at Google/Amazon/Meta?
What data structure is used in Keys and Rooms?
What is the time complexity of Keys and Rooms?
Ready to solve this problem?
Practice Keys and Rooms with our built-in code editor and test cases.
Practice on FleetCode