Problem Statement

Keys and Rooms

You have n rooms, labeled 0 up to n - 1. Every room is locked except room 0, which is already open. Inside a room you may find keys, and each key opens another room. The list called rooms tells you what is inside each one: rooms[i] is the list of keys you find in room i. Starting from room 0, you want to know if you can eventually open and visit every room. Return true if you can reach them all, and false if at least one stays locked forever. The picture to hold in your head is a map of dots connected by arrows. Each room is a dot, and a key from room i to room j is an arrow pointing from i to j. The question is just: starting at dot 0 and only following arrows, can you touch every dot? That is a graph reachability question, and the standard tool is to walk the graph from the start and see which dots you reach.

mediumGraphDFSGraphsTime: O(V+E) · Space: O(V)

Signals to notice

can you visit all rooms starting from room 0keys in rooms unlock other roomsreachability

Brute force first

No simpler alternative — graph traversal is the natural approach. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

BFS or DFS from room 0. Each room you enter gives you keys to other rooms. Track visited rooms. If all rooms are visited, return true. where E = total keys. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `rooms=[[1,3],[3,0,1],[2],[0]]`

init: visited={}, stack=[0]
pop 0 -> visit {0}; push keys 1,3 -> stack=[1,3]
pop 3 -> visit {0,3}; key 0 already visited -> stack=[1]
pop 1 -> visit {0,3,1}; keys 3,0,1 all visited -> stack=[]
stack empty; loop ends (room 2 never reached)
len(visited)=3 != len(rooms)=4 -> return false

What must stay true

Starting from room 0 with its keys, you can only enter rooms you have keys to. It's a reachability problem — can you reach all rooms from room 0 via the key graph? If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

visited = {}; stack = [0]
while stack:
    room = stack.pop()
    if room in visited: continue
    visited.add(room)
    for key in rooms[room]: stack.push(key)
return len(visited) == len(rooms)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not tracking visited rooms — without it, you could enter the same room multiple times and loop infinitely if there are cycles in the key structure. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Graphs Pattern