Keys and Rooms
Keys and Rooms is LeetCode 841 (Medium). There are n rooms numbered 0 to n - 1, and every room except room 0 starts locked. rooms[i] lists the keys lying in room i, and key j unlocks room j.
- You can enter any room you hold a key for, in any order, and you keep every key you pick up.
- Return
trueif you can enter every room, andfalseotherwise.
There are at most 1,000 rooms and 3,000 keys in total, so one pass over the rooms and keys is enough.
- n == rooms.length
- 2 <= n <= 1000
- 0 <= rooms[i].length <= 1000
- 1 <= sum(rooms[i].length) <= 3000
- 0 <= rooms[i][j] < n
- All the values of rooms[i] are unique.
Intuition
Draw each room as a node and each key as an arrow from the room it lies in to the room it opens. Room j can be entered exactly when a path of arrows leads from room 0 to it: walking that path picks up each key you need on the way.
So the question is whether every node can be reached from node 0, and one depth-first search from room 0 answers it. If the search marks all n rooms, the answer is true.
The arrows only go one way. A key to room 2 lying in room 1 says nothing about getting from room 2 back to room 1.
Whenever picking something up opens more things to pick up, and getting it costs nothing, the question is plain reachability: unlockable levels in a game, pages reachable by links, packages pulled in by a dependency.
Approach
Before reading on, restate the problem without keys or rooms: what is it asking about a directed graph? Then decide when a room should be marked so it is never handled twice. Aim for O(n + k), with k the total number of keys.
Mark room 0 and put it on the stack
Room 0 is open from the start, so mark it as seen and push it. A room is marked the moment its key is found, not when it is entered, so it can never be on the stack twice.
Pop a room and pick up its keys
Pop the top room from the stack; you are now inside it and hold all of its keys. Each key opens exactly one room, so the keys are the arrows to follow next.
Push each key's room the first time you see it
For a key to a room that is not marked yet, mark the room and push it. A key to a marked room, including a key to the room you are standing in, is ignored: that room is already waiting on the stack or done.
Compare the count with n
When the stack is empty, every room that can be reached has been marked. Return true only if the number of marked rooms equals n; a room left unmarked has no path of keys from room 0.
Keys and Rooms solution in Python | C++ | Java
Common pitfalls
Pushing rooms without marking them
for key in rooms[room]:
stack.append(key)for key in rooms[room]:
if key not in seen:
seen.add(key)
stack.append(key)For [[1], [0]], room 0 pushes room 1, room 1 pushes room 0, room 0 pushes room 1 again, and the loop never ends. The seen check is what breaks the cycle.
Counting keys instead of rooms you can reach
keys = {0}
for r in rooms:
keys.update(r)
return len(keys) == len(rooms)return len(seen) == len(rooms) # after the DFS
For [[1], [], [3], [2]] every room has a key somewhere, so this returns true. But the keys to rooms 2 and 3 lie inside rooms 3 and 2, which nothing you can reach opens. The answer is false.
Recursive DFS in Python on a long chain
def dfs(r):
seen.add(r)
for k in rooms[r]:
if k not in seen:
dfs(k)stack = [0]
while stack:
...Python stops recursion at a depth of 1,000 by default. For 1,000 rooms in a chain, [[1], [2], ..., [999], []], the calls nest about 1,000 deep and raise RecursionError. An explicit stack has no such limit.
Complexity
Keys and Rooms FAQ
Does BFS work too?
Yes. Swap the stack for a queue and nothing else changes. BFS reaches the same rooms in a different order, and the answer depends only on which rooms were reached, not when.
How is this different from Number of Provinces?
Number of Provinces counts the separate groups in an undirected graph, so it starts a new search from every unvisited city. Here the arrows have a direction and there is only one start, room 0, so a single search decides the answer.