Keys and Rooms — Reachability via BFS / DFS Traversal

Problem Statement#

LeetCode 841 — Keys and Rooms (Medium)

There are n rooms labeled from 0 to n - 1. All rooms are locked except room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks. You can take all of these keys with you to unlock other rooms.

Given an array rooms where rooms[i] is the set of keys you can find when you visit room i, return true if you can visit all the rooms, or false otherwise.

Constraints:

• n == rooms.length, with 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n and all values of rooms[i] are unique.

Example 1:

rooms = [[1],[2],[3],[]]
Output: true
Explanation: Start in 0, pick key 1, go to 1, pick key 2, go to 2, pick key 3, go to 3.

Example 2:

rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: Room 2 is never reachable — no other room contains key 2.

Why This Problem Matters#

This is one of the cleanest reachability problems in the LeetCode catalog and shows up at Google, Amazon, and Meta as a warm-up before harder graph questions. It tests three competencies in a single short prompt:

1. Graph modeling. Many candidates panic because the problem mentions rooms and keys instead of nodes and edges. The first skill the interviewer is checking is whether you can translate prose into a graph: rooms are nodes, keys are directed edges, and "visit all rooms" is "is every node reachable from node 0?"
2. BFS or DFS choice. Either traversal works because the problem only asks reachability, not shortest path. Interviewers want to see you justify the choice rather than blindly default to one.
3. Visited-set hygiene. A single missing visited check turns this into an infinite loop because keys can point back to already-visited rooms (see Example 2 where room 1 holds key 0).

Mastering this question prepares you for harder reachability questions like LC 1971 (Find if Path Exists in Graph), LC 547 (Number of Provinces), and LC 1129 (Shortest Path with Alternating Colors), all of which use the same template with one extra wrinkle.

The Core Insight#

The problem is equivalent to: starting at node 0 in a directed graph, can you reach every other node? The "keys" inside each room are simply the out-edges of that node. Once you reframe it that way, the algorithm is a textbook traversal.

The only nuance is that the graph is implicit. You do not get an adjacency list — you get rooms[i] which is exactly the adjacency list. So no preprocessing is needed; iterate over rooms[node] directly.

A subtle point: the keys inside a room are picked up the moment you enter, so the order in which you process them is irrelevant. Both BFS (level-by-level) and DFS (depth-first) yield the same reachable set, and both finish in linear time.

Visual Dry Run#

Take rooms = [[1,3],[3,0,1],[2],[0]] and run BFS from room 0.

Start: queue = [0], visited = {0}
 
Pop 0. rooms[0] = [1, 3].
  1 not visited: enqueue, visited = {0, 1}
  3 not visited: enqueue, visited = {0, 1, 3}
 
Pop 1. rooms[1] = [3, 0, 1].
  3 already visited, skip
  0 already visited, skip
  1 already visited, skip
 
Pop 3. rooms[3] = [0].
  0 already visited, skip
 
Queue empty. visited = {0, 1, 3}. Size 3, but n = 4.
Room 2 was never reached. Return false.

Notice how the visited check immediately stops cycles like room 1 holding key 1 itself. Without it, the algorithm would loop forever.

Solution (Optimal)#

Python#

from collections import deque
 
class Solution:
    def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
        n = len(rooms)
        visited = {0}                      # Room 0 is always unlocked
        queue = deque([0])                 # BFS frontier
 
        while queue:
            room = queue.popleft()         # Process the next reachable room
            for key in rooms[room]:        # Every key is a directed edge
                if key not in visited:     # Skip rooms we already entered
                    visited.add(key)       # Mark before enqueue to avoid duplicates
                    queue.append(key)
 
        # We visited every room iff the visited set covers all n labels
        return len(visited) == n

JavaScript#

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    const n = rooms.length;
    const visited = new Set([0]);          // Room 0 starts unlocked
    const queue = [0];
    let head = 0;                          // O(1) dequeue pointer
 
    while (head < queue.length) {
        const room = queue[head++];        // Pop the next room
        for (const key of rooms[room]) {   // Each key is an out-edge
            if (!visited.has(key)) {       // Skip already-entered rooms
                visited.add(key);          // Mark on enqueue, not on dequeue
                queue.push(key);
            }
        }
    }
 
    return visited.size === n;             // True iff every room reached
};

Complexity. Time is O(N + E) where N is the number of rooms and E is the total number of keys across all rooms. Each room is dequeued once and each key is examined once. Space is O(N) for the visited set and the BFS queue.

Common Mistakes#

1. Forgetting to mark room 0 as visited at the start. If room 0 appears as a key inside another room (Example 2 has key 0 inside room 1), you will enqueue it twice and inflate the visited count incorrectly with weaker logic.
2. Marking visited on dequeue instead of on enqueue. Marking on dequeue lets the same node enter the queue many times before it is processed. For dense graphs this blows up runtime.
3. Returning early without finishing. Some candidates check visited.size === n inside the loop. That works but is a micro-optimization; do not let it complicate the loop. Check size once at the end.
4. Treating the graph as undirected. Keys are directional. Just because room 1 has a key to room 2 does not mean room 2 has a key back. Do not add reverse edges.
5. Using recursion without an explicit stack on extreme inputs. With n up to 1000 and a chain-shaped graph the recursion depth in Python can hit the default limit and crash. Iterative BFS sidesteps this.

Interview Tips#

• State the model out loud. Say "I will model this as a directed graph where rooms are nodes and rooms[i] is the adjacency list. The question becomes whether node 0 reaches every other node." This single sentence proves you understand graphs and earns immediate trust.
• Justify BFS or DFS. Both work. Pick BFS if the interviewer hints at extending to shortest path; pick DFS if recursion feels cleaner. Mention the trade-off rather than choosing silently.
• Walk through Example 2. It is the failing case and forces you to demonstrate that the visited check correctly handles cycles.
• Mention the linearity. Saying "this is O(N + E) which is optimal because we must read every key in the worst case" signals algorithmic maturity.

Follow-up Questions#

1. What if you wanted the minimum number of rooms entered to reach a specific target room? Switch to BFS and track the depth of each node. Return the depth of the target.
2. What if some keys are limited-use (single-use)? This becomes a state-space search where state is (current_room, multiset_of_keys_held). Use BFS over that augmented state space.
3. How would you handle 10 to the 9 rooms streaming in? You cannot keep visited in memory. Use a Bloom filter for approximate membership, or process the graph in disk-backed chunks with an external BFS.
4. What if rooms had locks that require multiple keys? Treat each room's lock as a logical AND of incoming keys. Use a topological-style traversal where a room becomes accessible only when all required keys have been collected.

Key Takeaways#

• Keys and Rooms is a graph reachability problem in disguise; rooms are nodes and keys are directed edges.
• Either BFS or DFS solves it in linear O(N + E) time, visiting each node and edge exactly once.
• Mark visited on enqueue, not on dequeue, to prevent the same node from being scheduled multiple times.
• Initialize the visited set with room 0 so cycles back to the start cannot inflate or break the count.
• The pattern generalizes to LC 1971, LC 547, and LC 1129 with only minor tweaks to the visit predicate.
• Interviewers grade you on whether you explicitly translate the prose into graph terms before writing code.