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.In #841 Keys and Rooms, each room may contain keys to other rooms, forming a structure that can be modeled as a graph. The main goal is to determine whether all rooms can be visited starting from room 0. This naturally leads to a graph traversal strategy.
A common approach is to use either Depth-First Search (DFS) or Breadth-First Search (BFS). Start from room 0, collect the keys inside, and use them to explore additional rooms. Maintain a visited set or boolean array to avoid revisiting rooms and to track progress. Each time you obtain a key, treat it as an edge leading to another node (room) and continue the traversal.
The idea is to simulate unlocking rooms while ensuring that each room is processed at most once. If the traversal finishes and the number of visited rooms equals the total number of rooms, then all rooms are reachable. This approach runs efficiently because each room and key is processed only once.
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 visited tracking and traversal stack/queue.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (DFS) | O(n + e) | O(n) |
| Breadth-First Search (BFS) | O(n + e) | O(n) |
Nick White
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.
1def canVisitAllRooms(rooms):
2 visited = set()
3
4 def dfs(room):
5 if room not in visited:
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, the problem can be modeled as a directed graph where rooms are nodes and keys represent edges to other rooms. Graph traversal techniques like DFS or BFS are the most natural way to determine if all nodes can be reached from the starting node.
Yes, variations of graph traversal problems like Keys and Rooms frequently appear in FAANG-style interviews. They test understanding of DFS/BFS, visited tracking, and the ability to model real-world scenarios as graphs.
The optimal approach is to treat the rooms as nodes in a graph and traverse them using DFS or BFS starting from room 0. By collecting keys and marking visited rooms, you can determine whether all rooms are reachable. This ensures each room and key is processed only once.
A visited array or set is essential to track which rooms have already been explored. For traversal, you can use a stack for DFS or a queue for BFS. Both structures work efficiently since the problem is essentially a graph reachability task.
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.