Keys and Rooms: Graph Traversal Explained

You are given an array of rooms, where each room contains a list of keys. Room 0 is unlocked, and every other room starts locked. Can you visit all the rooms? This is LeetCode 841: Keys and Rooms, rated medium. Once you see the graph hiding behind the rooms, the solution clicks into place.

The problem

There are n rooms labeled from 0 to n - 1. All rooms are locked except for room 0. Each room contains a set of keys, and each key unlocks exactly one other room. You need to determine whether you can visit every room starting from room 0.

Input:  rooms = [[1],[2],[3],[]]
Output: True

Room 0 has key 1, room 1 has key 2, room 2 has key 3, and room 3 is empty. Starting from room 0, you can collect keys and eventually reach every room.

Input:  rooms = [[1,3],[3,0,1],[2],[0]]
Output: False

Here, room 2 is never reachable. No room contains key 2, so it stays locked forever.

The key insight: this is a graph reachability problem

Each room is a node. Each key in a room is a directed edge from that room to the room the key opens. Room 0 contains key 1, so there is an edge from node 0 to node 1. Room 1 contains key 2, so there is an edge from node 1 to node 2. And so on.

The question "can you visit all rooms?" becomes "can you reach all nodes from node 0 in this directed graph?" That is a classic graph reachability problem, and both DFS and BFS solve it cleanly.

Step-by-step walkthrough

The code

def can_visit_all_rooms(rooms):
    visited = set()
    stack = [0]

    while stack:
        room = stack.pop()
        if room in visited:
            continue
        visited.add(room)
        for key in rooms[room]:
            if key not in visited:
                stack.append(key)

    return len(visited) == len(rooms)

This is an iterative DFS using an explicit stack. We start by pushing room 0 onto the stack. Each iteration pops a room, marks it as visited, and pushes all its keys (the rooms those keys unlock) onto the stack. If a key leads to a room we have already visited, we skip it. At the end, if the visited set contains every room, we return True.

The visited set is doing the same job it does in any graph traversal: preventing infinite loops and redundant work. Without it, a room that appears as a key in multiple other rooms would be processed over and over.

Complexity analysis

Where n is the number of rooms and k is the total number of keys across all rooms.

Time: We visit each room at most once (O(n)), and we iterate through each key at most once (O(k)). Total: O(n + k).

Space: The visited set holds at most n entries. The stack also holds at most n entries in the worst case. Total: O(n).

The building blocks

Graph reachability via DFS

The core pattern here is starting from a source node, tracking which nodes you have visited, and exploring all reachable neighbors. This same pattern appears in dozens of graph problems.

def reachable_from(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

    return visited

The input to Keys and Rooms already gives you the adjacency list. rooms[i] is the list of neighbors for node i. You do not need to build any extra data structure. Just feed it directly into the traversal.

Edge cases

• Single room: rooms = [[]]. Room 0 is unlocked and there are no other rooms. Return True.
• Room with key to itself: rooms = [[0, 1], []]. Room 0 has key 0 (itself). The visited set handles this naturally, skipping the duplicate.
• Rooms with duplicate keys: rooms = [[1, 1, 1], []]. Multiple copies of the same key do not cause problems. The visited check prevents re-processing.
• Disconnected rooms: rooms = [[1], [], [3], []]. Rooms 2 and 3 are not reachable from room 0. No key chain leads to room 2, so the visited set will be smaller than the number of rooms. Return False.
• Fully connected: every room has keys to every other room. The traversal visits everything on the first pass. Return True.

From understanding to recall

You have seen how Keys and Rooms maps directly to graph reachability. The DFS solution is short, just a stack and a visited set. The logic is clean. But recognizing the graph structure under time pressure and writing it correctly from memory are two different skills.

The details matter. Using a set for visited instead of a list. Checking if room in visited before processing. Comparing len(visited) == len(rooms) at the end instead of trying to track it during traversal. These are small decisions, but getting any of them wrong costs you time during an interview.

Spaced repetition makes these decisions automatic. You practice writing the DFS traversal from scratch at increasing intervals until the pattern flows without hesitation. After a few rounds, you see "can you reach all nodes" and your hands just type the solution.

Related posts

• Number of Islands - DFS on a grid to find connected components
• Clone Graph - Graph traversal with node copying
• Course Schedule - Directed graph traversal for cycle detection

Keys and Rooms is one of the cleanest introductions to directed graph reachability. Once you internalize the pattern of "rooms are nodes, keys are edges, check if all nodes are reachable," you can apply that same thinking to any reachability problem. CodeBricks drills this pattern with spaced repetition so it becomes second nature.