Keys and Rooms
Problem statement
There are n rooms, numbered 0 to n - 1. Room 0 is open; every other room is locked. rooms[i] lists the keys lying in room i, and each key opens the room with that number. You can carry every key you pick up.
Return true if, starting in room 0, you can get into every room, and false otherwise.
The same shape shows up in service discovery: a new node knows only one seed, each node it contacts hands over the addresses of others, and you want to know whether it can discover the whole cluster.
Examples
Example 1
Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: Room 0 holds the key to room 1, room 1 holds the key to room 2, and room 2 holds the key to room 3. Following that chain opens all four rooms.
Example 2
Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: Rooms 0, 1 and 3 give keys only to rooms 0, 1 and 3. The one key to room 2 is locked inside room 2, so it can never be reached.
Hints
i as a one-way edge from i to the room it opens. What is the question in graph terms?Approach
Optimal: BFS with a queue
Intuition
Same walk, different order. Instead of always using the newest key, use the oldest one first: put rooms in a queue (first in, first out). This is a breadth-first search (BFS). It opens rooms in "rings": first every room room 0 unlocks, then every room those unlock, and so on.
The order doesn't change which rooms you can reach, so the answer is the same as DFS. BFS is handy when a follow-up asks for the fewest rooms you must pass through to reach a given room, because it reaches each room by the shortest chain of keys first.
Steps
- Create
visited, mark room 0, and put 0 in a queue. Setopened = 1. - While the queue isn't empty:
- Take the front room.
- For each key in it whose room isn't visited: mark it, add 1 to
opened, and add it to the back of the queue.
- Return
opened == n.
Dry run
rooms = [[1],[2],[3],[]]
| take | newly opened | queue after | opened |
|---|---|---|---|
| start | 0 | [0] | 1 |
| 0 | 1 | [1] | 2 |
| 1 | 2 | [2] | 3 |
| 2 | 3 | [3] | 4 |
| 3 | none (no keys) | [] | 4 |
opened = 4 = n → true.
Complexity
Time O(n + K) - Each room enters the queue at most once, since it is marked visited when it is added. Each key is looked at once, when its room is taken out of the queue. So the total work is the same as DFS: one step per room and one per key.
Space O(n) - The `visited` list is n flags, and the queue holds at most n rooms. No recursion is used. The input is not counted.
from collections import deque
from typing import List
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
n = len(rooms)
visited = [False] * n
visited[0] = True
queue = deque([0])
opened = 1
while queue:
room = queue.popleft()
for key in rooms[room]:
if not visited[key]:
visited[key] = True
opened += 1
queue.append(key)
return opened == n
if __name__ == "__main__":
print(str(Solution().canVisitAllRooms([[1], [2], [3], []])).lower()) # true
print(str(Solution().canVisitAllRooms([[1, 3], [3, 0, 1], [2], [0]])).lower()) # falseRecapThe whole problem in a few lines, for the night before
- Spot it: rooms with keys to other rooms, can you visit all starting from room 0
- Idea: DFS or BFS from room 0 over the keys, mark rooms visited, then check that the visited count equals the number of rooms
- Cost: O(rooms + keys) time, O(rooms) space
- Trap: mark a room visited before pushing it, so repeated keys do not cause repeated work
Interview follow-ups
Return the rooms you can never enter, not just true or false.
Run the same walk, then list every room whose
visitedflag is stillfalse. That's one extra pass over n flags, so the time stays O(n + K). In the infra version this is the list of nodes a new member can never discover — exactly what you'd want in an alert.What's the fewest rooms you must enter to reach room
t?Use BFS and store the distance of each room when you first open it:
dist[key] = dist[room] + 1. BFS opens rooms in order of distance, so the first time you opentgives the shortest chain. Time and space stay O(n + K).Keys are now shared between buildings, and new keys can appear over time. How do you keep the answer up to date?
When a new key
a → bappears, check whether roomais already reachable. If it is andbisn't, run the walk frombonly, opening just the rooms that became reachable. Each room is still opened at most once in total, so the total work over all updates stays O(n + K).
Frequently asked questions
You could keep rescanning every opened room's keys until nothing new opens, but that is just a slower way to do the same walk. The input already is an adjacency list (room → rooms it unlocks), so DFS or BFS can start straight away with no setup. Both visit each room and each key once, which is the minimum any correct method needs.
Keys are one-way. A key in room 1 for room 2 does not mean room 2 has a key back to room 1. Union-find treats every link as two-way, so it would wrongly say room 2 "connects" to room 1 and could report true when the answer is false. For one-way edges, walk the graph from the start instead.
Usually yes: there are at most 1,000 rooms, so the recursion is at most 1,000 calls deep. That is right at Python's default limit of 1,000, though, so a long chain of rooms can still fail there. An explicit stack avoids the question entirely and is just as short.
Both work. Counting as you go lets you compare one number with n at the end, instead of scanning the whole visited list again. It also lets you stop early: if opened reaches n in the middle of the walk, you can return true right away.
It is reachability on a directed graph, which is how dependency and access questions look in practice. Can a bootstrap node discover the whole cluster from its seed list? Starting from one set of credentials, which systems can an attacker eventually reach? Is every page of an internal docs site reachable from the home page? Each is "start at one node and see what you can open".