Keys and Rooms

Problem

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. When you visit a room, you may find a set of distinct keys in it. Return true if you can visit all the rooms, or false otherwise.

Examples

The brute-force approach

BFS/DFS from room 0. Collect all keys found. Repeat until no new rooms can be unlocked. Check if all rooms were visited.

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)

O(n + k) where k is total keys — this is already the optimal approach.

Spotting the pattern

This is a Graph Traversal problem. The key question to ask yourself:

This is a reachability problem starting from room 0. What data structure tells you which rooms you've already visited, and why does that prevent infinite loops?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.