Keys and Rooms: A Graph Reachability Question in Disguise

The problem

There are n rooms, all locked except room 0. Each room holds a list of keys to other rooms. Return true if you can visit every room.

Spot the graph

Each room is a node and each key is a directed edge. The question is simply: is every node reachable from node 0? Saying this out loud early turns a wordy puzzle into a standard traversal, and it is usually the moment the interviewer relaxes.

Iterative DFS

def can_visit_all_rooms(rooms):
    seen = {0}
    stack = [0]
    while stack:
        room = stack.pop()
        for key in rooms[room]:
            if key not in seen:
                seen.add(key)
                stack.append(key)
    return len(seen) == len(rooms)

Mark a room as seen when you push it, not when you pop it. That keeps each room on the stack at most once.

BFS works just as well

Swap the stack for a deque and popleft(). Order does not matter here because you only need reachability, not shortest distance. If asked which to prefer, say iterative DFS or BFS avoids recursion depth limits when n is large.

Complexity

O(n + k) time where k is the total number of keys, and O(n) space for the seen set and stack.

Edge cases worth naming

Follow-ups

Interviewers sometimes ask for the minimum number of rooms you must open to reach room t (that is BFS distance), or which rooms stay locked (the complement of seen). Both drop out of the same code.


Disclosure: I work on Linkjob AI. If you want structured practice for interviews like this, AI coding interview assistant can help you rehearse and get real-time hints.