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?” There’s no naive variant that avoids traversing the graph — you can’t decide reachability without following edges. A tempting non-answer is “return True iff every room is named as a key somewhere,” but that’s wrong: keys can form an unreachable cluster (rooms = [[1,3],[3,0,1],[2],[0]] — room 2 is keyed by room 2 itself, yet 2 is unreachable). So we go straight to traversal.

Approach 2 — DFS (recursion)

The insight: 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) don’t loop forever. Reachable rooms are exactly those DFS touches.

class Solution:
    def canVisitAllRooms(self, 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)

The insight: identical reachability, explored breadth-first with a queue. Mark a room visited when you enqueue it (not when you pop it) to avoid adding the same room twice. BFS is preferred when recursion depth is a worry — a chain of 1000 rooms could approach Python’s recursion limit under DFS; BFS uses an explicit queue and is safe. DFS wins on brevity for shallow graphs.

from collections import deque


class Solution:
    def canVisitAllRooms(self, 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’s reachability in disguise — pick BFS for depth safety, DFS for concise code.