DSA sheet · Graphs · BFS pattern · single-source reachability

Keys and Rooms

A story about locked rooms and keys that turns out to be the simplest graph question there is: start from room 0 and check whether a traversal can reach every room. The teacher spots that the input is already an adjacency list (the keys in a room are the rooms you can go to next), explains BFS on the two examples, gives two ways to decide "did I visit everything?" (scan the visited array, or count the rooms that came out of the queue), and then codes the DFS version. It's a good warm-up for spotting "this is just reachability" inside a wordy problem.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics this page needs
• Part A · BFS from room 0
• Part B · DFS from room 0 (the teacher's code)
• Part C · Revision page

Part 0 · Graph basics this page needs

Nodes and edges

A graph is a set of nodes (points) joined by edges (lines). Here every room is a node, and "room a holds the key to room b" is an edge from a to b: once you're in a, you can go to b.

Directed, undirected, weighted

Three ways the input can arrive, and the adjacency list

Look at the last row: that's exactly the input format of this problem. rooms[u] is the list of keys in room u, i.e. the rooms you can go to from u. The teacher's point: normally the first job in a graph problem is to build an adjacency list so we know a node's "children"; here rooms already is one, so we skip that step. For other problems, this is how you'd build one from an edge list:

n = 4
edges = [[0, 1], [1, 2], [2, 3]]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)           # directed: only u -> v
print(adj)                     # [[1], [2], [3], []]

The visited array

Rooms can hold keys to rooms we've already seen, even to themselves or back to room 0 (Example 2 does this). Without a record of "already been here", we'd keep walking the same rooms in a loop. So we keep visited, one True/False per room, and only enter a room that is not visited yet.

Single source, and connected components

Usually we loop over every node and start a new traversal from each unvisited one, because the graph may be in several pieces (connected components). Here the problem fixes the start: only room 0 is open. That makes it a single-source question: one traversal from 0, then ask "did it reach everyone?" If some room sits in a piece that 0 can't reach, the answer is False.

BFS and DFS

Part A · BFS from room 0

LeetCode 841 · Keys and Rooms

1The question in simple words

There are n rooms, numbered 0 to n−1. All are locked except room 0. Inside each room is a set of keys; key k opens room k. You can pick up every key you find and use it later. rooms[i] lists the keys in room i. Return True if you can get into every room, otherwise False.

(0)→(1)→(2)→(3)

room 0 has key 1, room 1 has key 2,
room 2 has key 3, room 3 is empty
all 4 rooms reachable → True

(0) ⇄ (1)↺       0→1 0→3
 ⇅   ↙           1→3 1→0 1→1 (its own key)
(3)              3→0

(2)↺             key 2 is only inside room 2
room 2 never opens → False

2What the constraints tell us

• 2 ≤ n ≤ 1000 → at least 2 rooms, so there is always something to check after room 0.
• 0 ≤ rooms[i].length ≤ 1000 → a room can be empty (no keys) or hold many. The teacher's remark: with at most 1000 rooms, a room can't usefully hold more than 1000 different keys.
• The total number of keys over all rooms is at most 3000, and the keys in one room are all different. So scanning every key once is tiny.
• For the DFS in Part B: a chain of 1000 rooms means 1000 nested calls, right at Python's default recursion limit (about 1000). We'll need to raise it.

3Intuition: a treasure hunt

Stand in room 0 with an empty bag. Pick up every key you see. Keep a list of "rooms I can open but haven't explored yet". Explore them one by one, picking up more keys. When the list runs out, look back: did you get into every room? The teacher's summary: the only task is to visit all the rooms we can, so it's just a DFS or BFS traversal that marks rooms visited.

4Building the logic from the teacher's examples

Example 1, with a queue

Put room 0 in the queue. Pop 0: it has key 1, so add room 1. Pop 1: key 2, add room 2. Pop 2: key 3, add room 3. Pop 3: no keys. The queue is empty and we went into all 4 rooms → True.

Only add rooms we haven't seen

Mark a room visited the moment we add it to the queue, and only add rooms that are not visited. Two good things follow: no room goes into the queue twice, and loops like "room 1 holds the key to room 0" can't trap us.

Two ways to answer "did I visit everything?"

1. Scan the visited array. After the BFS, if any room is still False, we never got in → return False. Otherwise True.
2. Count. Because each room enters the queue at most once, the number of rooms popped from the queue equals the number of different rooms we entered. Keep count += 1 on every pop, and at the end compare count == len(rooms).

Example 2, and the teacher's slip

While walking through Example 2 she first misreads one of the lists and finds that every room opens, then notices the mismatch and redoes it with the real input. The correct walk: pop 0 → keys 1 and 3, both new, push them. Pop 1 → keys 3, 0, 1, all already visited, push nothing. Pop 3 → key 0, visited. The queue is empty. We popped 3 rooms but there are 4. Room 2 never opened, because its only key is locked inside room 2 itself → False.

5Approach steps

1. visited = [False] * n; mark room 0 and push it.
2. While the queue isn't empty: pop a room, add 1 to count.
3. For each key in that room: if the room it opens isn't visited, mark it and push it.
4. Return count == n.

6Code (Python)

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms):
        n = len(rooms)
        visited = [False] * n
        visited[0] = True                 # room 0 is open
        q = deque([0])
        count = 0
        while q:
            room = q.popleft()
            count += 1                    # one more distinct room entered
            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    q.append(key)
        return count == n                 # or: return all(visited)

7Code line by line

8Dry run

Example 2: rooms = [[1,3],[3,0,1],[2],[0]]

Example 1: rooms = [[1],[2],[3],[]]

9Complexity & remember

• Time O(n + K), where K is the total number of keys. Each room is pushed and popped at most once (that's the n), and each room's key list is read once, when that room is popped (that's the K). The teacher's way of saying it: don't multiply n by n just because there's a loop inside the while loop. Even if the first room holds keys to all the others, every room still enters the queue only once.
• Space O(n): the visited array plus the queue (only unvisited rooms are ever pushed).

Part B · DFS from room 0

After explaining BFS, the teacher codes the DFS version, saying that anyone following the playlist should be able to write both for a pure traversal problem. Steps ①–④ are the same as Part A. What changes:

• No queue and no count. A recursive dfs(room) marks the room and calls itself on every key whose room isn't visited yet.
• The function returns nothing; its only job is to fill visited.
• At the end we use way 1: scan visited; any False means a room we couldn't enter.

5Approach steps

1. visited = [False] * n; call dfs(0).
2. dfs(room): mark it True; for each key, if that room isn't visited, call dfs(key).
3. After the call: if any entry of visited is False → False, else True.

6Code (Python)

import sys

class Solution:
    def canVisitAllRooms(self, rooms):
        sys.setrecursionlimit(10000)
        visited = [False] * len(rooms)

        def dfs(room):
            visited[room] = True
            for key in rooms[room]:
                if not visited[key]:
                    dfs(key)

        dfs(0)
        for v in visited:
            if not v:
                return False              # a room we never got into
        return True

7Code line by line

8Dry run

Example 2: rooms = [[1,3],[3,0,1],[2],[0]]

In Example 1 the calls go straight down 0 → 1 → 2 → 3, every room gets marked, the scan finds no False → True.

9Complexity & remember

• Time O(n + K): each room is entered once and its keys read once.
• Space O(n): the visited array plus up to n calls on the recursion stack.

Part C · Revision page

s = Solution()
print(s.canVisitAllRooms([[1], [2], [3], []]))                 # True
print(s.canVisitAllRooms([[1, 3], [3, 0, 1], [2], [0]]))       # False
print(s.canVisitAllRooms([[1], []]))                           # True
print(s.canVisitAllRooms([[], [0]]))                           # False
print(s.canVisitAllRooms([[1, 2, 3], [], [], []]))             # True

Based on this video: Keys and Rooms | Graph | Pattern-wise DSA sheet