Keys and Rooms

Problem

There are n rooms labeled 0 to n - 1. You start in room 0, and every other room is locked. Each room i contains a list rooms[i] of keys, where each key is the label of a room it unlocks.

Return True if you can enter all n rooms, False otherwise.

You may pick up keys from a room the first time you enter it and use them to open other rooms; keys can be used any number of times.

Examples

• rooms = [[1],[2],[3],[]] → True — 0 gives key 1, 1 gives key 2, 2 gives key 3; all four visited.
• rooms = [[1,3],[3,0,1],[2],[0]] → False — room 2 is never referenced by any key you can reach, so it stays locked.
• rooms = [[1],[],[0,2]] → False — from 0 you get key 1, room 1 is empty, and nothing ever hands you key 2.

Constraints

• n == len(rooms), 2 <= n <= 1000.
• 0 <= sum(len(rooms[i])) <= 3000.
• Keys are valid room labels; a room may list duplicate keys and may list its own label.

Think about it first

TL;DR

Graph reachability from room 0 — DFS or BFS, then check every room was visited. O(V + E) time, O(V) space.

Approach 1 — Why there’s no cheaper brute force

The task is exactly “which nodes are reachable from node 0?” You cannot decide reachability without following edges, so there is no cheaper brute force. One wrong shortcut is “return True if every room is named as a key somewhere.” That fails because keys can form an unreachable cluster. In rooms = [[1,3],[3,0,1],[2],[0]], room 2 is keyed only by room 2 itself, so no reachable room ever hands you that key:

flowchart LR
    0 --> 1
    0 --> 3
    1 --> 0
    1 --> 3
    3 --> 0
    2 --> 2

Rooms 0, 1, and 3 form the component reachable from 0; room 2 sits outside it, keyed only by itself. Mere mention of a room as a key is not enough, so we traverse.

Approach 2 — DFS (recursion)

Entering a room grants its keys, which are edges to more rooms. Recurse into each newly unlocked room, guarding with a visited set so cyclic keys (room A holds a key to B, B holds a key to A) do not loop forever. The reachable rooms are exactly those DFS touches.

def canVisitAllRooms(rooms: list[list[int]]) -> bool:
    visited = set()

    def dfs(room: int) -> None:
        visited.add(room)
        for key in rooms[room]:
            if key not in visited:
                dfs(key)

    dfs(0)
    return len(visited) == len(rooms)

Walkthrough (rooms = [[1],[2],[3],[]]):

• dfs(0): visit 0, key 1 unseen → dfs(1): visit 1, key 2 → dfs(2): visit 2, key 3 → dfs(3): visit 3, no keys.
• visited = {0,1,2,3}, size 4 = len(rooms) → True.
• On [[1,3],[3,0,1],[2],[0]]: DFS reaches {0,1,3} but never gets a key to 2 → size 3 ≠ 4 → False.

Complexity: each room is entered once, each key examined once → O(V + E) time (V rooms, E total keys), O(V) space for visited and the recursion stack.

Approach 3 — BFS (queue)

Same reachability, explored breadth-first with a queue. Mark a room visited when you enqueue it, not when you pop it, so the same room is never added twice. Use BFS when recursion depth is a concern: a chain of 1000 rooms could approach Python’s recursion limit under DFS, while BFS uses an explicit queue. DFS is more concise for shallow graphs.

from collections import deque


def canVisitAllRooms(rooms: list[list[int]]) -> bool:
    visited = {0}
    queue = deque([0])
    while queue:
        room = queue.popleft()
        for key in rooms[room]:
            if key not in visited:
                visited.add(key)
                queue.append(key)
    return len(visited) == len(rooms)

Walkthrough (rooms = [[1],[],[0,2]]): start visited={0}, queue [0]. Pop 0 → key 1 unseen, add → queue [1]. Pop 1 → no keys. Queue empties. visited = {0,1}, size 2 ≠ 3 → False (room 2 unreachable — nothing gives key 2).

Complexity: O(V + E) time, O(V) space — same as DFS.

Common pitfalls

• Forgetting the visited guard: rooms holding keys to each other (or a room listing its own label) send an unguarded traversal into an infinite loop.
• Marking BFS rooms visited on dequeue instead of enqueue, which can queue the same room multiple times and inflate work (still correct, just wasteful).
• Concluding True because every room label appears as a key somewhere — reachability, not mere mention, is what counts.
• Starting anywhere but room 0, or forgetting room 0 itself counts as visited from the outset.

Pattern takeaway

“Can I reach all nodes from a start?” is the most basic graph traversal: DFS or BFS from the source, mark visited, compare the visited count to the total. Whenever a problem describes objects that unlock other objects (keys, teleporters, dependencies), it is a reachability problem: pick BFS for depth safety, DFS for concise code.