Keys and Rooms
Keys and Rooms: each room holds keys to other rooms. Starting unlocked in room 0, return true if you can visit every room.
- n == rooms.length
- 2 <= n <= 1000
- 0 <= rooms[i].length <= 1000
- 0 <= rooms[i][j] < n
- All the values of rooms[i] are unique.
Intuition
Rooms are nodes and keys are directed edges, so 'can I visit every room' is simply 'is every node reachable from node 0'. Run one traversal from room 0, mark what you reach, and compare the count against the number of rooms.
Any puzzle where items unlock access to further items is a reachability question in disguise — 'can I get everywhere from here'. The tell is that acquiring something has no cost and no ordering constraint, which rules out shortest paths or DP and leaves a plain traversal.
Approach
Before reading on: restate the problem without mentioning keys or rooms. What is it asking about a directed graph? Aim for O(n + k).
Recognising the graph
The narrative hides an ordinary reachability question. Room i containing key j is a directed edge from i to j. Nothing about keys behaves specially — collecting a key you already hold changes nothing, and there is no cost or ordering constraint. Once framed this way, the entire problem is a single-source reachability check, which is the most basic graph traversal there is.
One traversal, with a visited set
Start a DFS or BFS at room 0 and mark it visited. For each key found in the current room, if that room is unvisited, mark it and traverse into it. The visited set is doing double duty: preventing infinite loops when rooms hold keys to each other, and recording the answer. Either traversal order works — the question asks only whether rooms are reachable, not by what route or in how many steps.
The final comparison
When the traversal ends, len(visited) is the number of reachable rooms. Compare it with len(rooms): equal means everything was reached. There is no need to check each room individually. Every room is enqueued at most once and every key is examined once, so the cost is O(n + k) where k is the total number of keys — linear in the size of the input.
Solution & live demo
Common pitfalls
Not marking rooms as visited
for key in rooms[room]:
stack.append(key)if key not in visited:
visited.add(key)
stack.append(key)Rooms holding keys to each other create a cycle, so without the check the stack grows forever and the loop never ends.
Marking on pop instead of on push
room = stack.pop() visited.add(room)
visited.add(key) stack.append(key)
Both are correct in the end, but marking at pop time lets the same room be pushed many times before it is first processed, bloating the stack. Marking at push time keeps each room on it at most once.
Checking rooms individually at the end
for i in range(len(rooms)):
if i not in visited:
return Falsereturn len(visited) == len(rooms)
It works but is unnecessary — the visited set already knows how many rooms were reached, so a single size comparison suffices.
Edge cases
Room 0 is visited at the start, so the answer is true.
Room 2 has no incoming key, so the traversal never reaches it and the answer is false.
The visited check makes a key to an already-visited room a no-op.
A room with no keys simply contributes no further edges.
The visited set stops the traversal from looping forever.