Keys and Rooms LeetCode 841 Guide

LeetCode 841 — Keys and Rooms — gives you n rooms labeled 0 through n-1. Room 0 starts unlocked. Every other room is locked, but each room contains a list of keys to other rooms. Starting from room 0, you can collect keys and use them to enter locked rooms. The question: can you visit every room?

The problem is a single yes/no reachability question. You need to determine whether all n rooms are reachable from room 0 given the directed key relationships. The rooms field is a list of lists: rooms[i] contains the keys found inside room i. Keys can repeat, and you may have keys to rooms you have already visited.

The constraints keep the problem manageable and make brute-force unnecessary. A systematic graph traversal is sufficient to visit all reachable rooms in one pass.

Rooms are nodes in a directed graph. Keys are directed edges: a key k found in room i means there is a directed edge from node i to node k. Room 0 is the source node. The question becomes: starting at node 0, can you reach every other node by following directed edges?

This is exactly the definition of graph reachability from a single source. The visited set tracks which rooms have been entered. When the traversal ends, if visited.size equals n, all rooms were reachable. If visited.size is less than n, at least one room had no path of keys leading to it from room 0.

Once you see the graph framing, the algorithm writes itself. Reach for your standard DFS or BFS template, substitute rooms for nodes and keys for neighbors, and check the visited count at the end. No specialized data structure or clever trick is needed — this is pure traversal.

The DFS solution starts by adding room 0 to the visited set, then recursively visits every room reachable via keys. For each room visited, iterate its key list; for each key that points to an unvisited room, mark it visited and recurse into it. After DFS completes, compare the size of the visited set to n.

The visited set serves two roles: it prevents revisiting rooms already entered (avoiding infinite cycles if keys loop back) and it provides the final count for the reachability check. Every room added to visited is a room that was successfully entered. A final count of n means every room was entered.

DFS is naturally recursive in Python and most interview languages. The call stack depth is at most n, which is safe given the constraint n <= 1000. An iterative DFS with an explicit stack is also straightforward and avoids any recursion limit concerns in Python for larger inputs.

The BFS solution uses a queue instead of recursion. Initialize the queue with room 0 and mark it visited. While the queue is non-empty, dequeue a room, iterate its keys, and enqueue any unvisited rooms while marking them visited. After the queue empties, check if visited.size equals n.

BFS processes rooms level by level — first room 0, then all rooms reachable directly from room 0, then rooms reachable in two hops, and so on. The order of discovery differs from DFS, but the final visited set is identical for any given input. BFS is often preferred in interviews by candidates who find iterative code easier to write without bugs under pressure.

Both approaches have O(V + E) time complexity where V is the number of rooms and E is the total number of keys across all rooms. Space complexity is O(V) for the visited set plus the stack or queue. For this problem, V <= 1000 and total keys <= 3000, so both are very fast in practice.

Example 1: rooms = [[1],[2],[3],[]]. Room 0 contains key 1. Room 1 contains key 2. Room 2 contains key 3. Room 3 contains no keys. DFS from 0: visit 0 → find key 1 → visit 1 → find key 2 → visit 2 → find key 3 → visit 3 → no keys. visited = {0,1,2,3}. Size 4 == n 4 → return true.

Example 2: rooms = [[1,3],[3,0,1],[2],[0]]. Start at room 0 → keys 1 and 3. Visit 1 → keys 3, 0, 1 (all visited or about to be). Visit 3 → key 0 (already visited). From the initial traversal, room 2 is never reached because no room reachable from 0 holds key 2 (room 2 only holds key 2, and you need to enter room 2 to get it — a catch-22). visited = {0,1,3}. Size 3 != n 4 → return false.

The second example illustrates why the problem is non-trivial: a room can be permanently inaccessible if its key is only found inside itself or inside other inaccessible rooms. The visited set naturally captures this — any room not added during traversal was never reachable.

Python DFS with a set: def canVisitAllRooms(rooms): visited = {0}; def dfs(room): [dfs(key) for key in rooms[room] if key not in visited and not visited.add(key)]; dfs(0); return len(visited) == len(rooms). Cleaner iterative DFS: visited = {0}; stack = [0]; while stack: room = stack.pop(); for key in rooms[room]: if key not in visited: visited.add(key); stack.append(key); return len(visited) == len(rooms). Time: O(V+E). Space: O(V).

Java DFS with a Set: public boolean canVisitAllRooms(List<List<Integer>> rooms) { Set<Integer> visited = new HashSet<>(); visited.add(0); Deque<Integer> stack = new ArrayDeque<>(); stack.push(0); while (!stack.isEmpty()) { int room = stack.pop(); for (int key : rooms.get(room)) { if (visited.add(key)) { stack.push(key); } } } return visited.size() == rooms.size(); }. HashSet.add returns false if the element was already present, so the visited.add(key) check doubles as the "not yet visited" guard.

Both implementations follow the same structure: initialize visited and a frontier (stack or queue) with room 0, expand until the frontier is empty, then compare visited size to total rooms. The Python iterative and Java versions are nearly identical in structure and are the safest to write from memory under interview pressure.

Number of Islands (LeetCode 200) uses the same DFS/BFS flood-fill pattern but on a 2D grid. Each unvisited land cell triggers a new traversal that marks the entire connected component visited. The count of traversals equals the number of islands. Keys and Rooms is structurally identical but on a directed adjacency list instead of a grid — the visited-set logic is the same.

Number of Provinces (LeetCode 547) — also called Friend Circles — asks for the number of connected components in an undirected graph given an adjacency matrix. Again the same visited-set DFS/BFS template: iterate all nodes, start a new traversal from each unvisited node, count traversals. Keys and Rooms is the single-source version: one traversal from node 0 determines if everything is in the same reachable component.

Course Schedule (LeetCode 207) extends graph traversal to detect directed cycles. Reachability from a source (Keys and Rooms) is simpler than cycle detection, but both use DFS on a directed graph with a visited/state array. Mastering the reachability template in Keys and Rooms provides the foundation for tackling the cycle-detection variant in Course Schedule.