841. Keys and Rooms

Problem¶

Starting in unlocked room 0, collect keys from every room you enter. Return whether those keys make all rooms reachable.

rooms = [[1, 3], [2], [], []]
0 -> keys {1, 3} -> room 1 gives key 2
visited = {0, 1, 2, 3}
output = True

Key trick¶

Model rooms as a directed graph: each key is an edge, so the answer is whether a DFS or BFS from room 0 reaches all nodes.

Trap¶

Treating the graph as undirected.
Revisiting rooms and looping on cycles.
Using recursive DFS in Python, since a chain near length 1000 can exceed the recursion limit.

Why is it interesting?¶

It hides a standard graph-reachability problem inside a real-world description.

Python solution¶

class Solution:
    def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        visited[0] = True
        stack = [0]
        cnt = 1

        # Visit every room reachable using collected keys.
        while stack:
            room = stack.pop()

            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    cnt += 1
                    stack.append(key)

        return cnt == n

Time complexity: \(O(n + k)\), where \(k\) is the total number of keys.

Space complexity: \(O(n)\).

Comment on my solution¶

Your reachability idea and cycle handling are correct, and the early return is valid. However, recursive DFS can raise RecursionError on a valid chain of roughly 1000 rooms, so iterative traversal is safer; also, “reachability from node 0” is more precise than “component” because the graph is directed.

# Ideas:
# - this is a component finding (a reachability problem)
#   - we want to know if there's a maximal compenent passing through all nodes
#   - start dfs from node 0

class Solution:
    def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
        n = len(rooms)
        visited = set()
        def dfs(node):
            visited.add(node)
            if len(visited) == n:
                return True
            for nei in rooms[node]:
                if nei not in visited:
                    if dfs(nei):
                        return True
            return False

        return dfs(0)