Keys and Rooms

Problem in plain words

There are n rooms numbered 0 to n - 1. Only room 0 is unlocked at the start. Each room contains a list of keys, and key x opens room x. You may enter any room you have a key for, collect its keys, and repeat. Return true if you can eventually enter every room.

Example: rooms = [[2], [], [1]]. Room 0 gives key 2, room 2 gives key 1, and room 1 is then open, so the answer is true. With [[1], [], [0]], nothing ever opens room 2, so the answer is false.

Intuition

Treat each room as a node and each key as a directed edge from the room containing it to the room it opens. The question becomes: are all nodes reachable from node 0? That is a plain reachability search — a depth-first search (or BFS) with a visited array.

Approach

1. Create a boolean visited array, mark room 0 visited and push it on a stack.
2. Pop a room and look at each key in it.
3. If the key's room is not visited yet, mark it and push it.
4. When the stack is empty, return true only if every room is marked (or the visited count equals n).

Dry run

rooms = [[2], [], [1]]

Visited = {0, 1, 2}, all three rooms, so return true.

Java solution

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        visited[0] = true;
        stack.push(0);
        int count = 1;
        while (!stack.isEmpty()) {
            int room = stack.pop();
            for (int key : rooms.get(room)) {
                if (!visited[key]) {
                    visited[key] = true;
                    count++;
                    stack.push(key);
                }
            }
        }
        return count == n;
    }
}

Python solution

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False] * len(rooms)
        visited[0] = True
        stack = [0]
        while stack:
            room = stack.pop()
            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    stack.append(key)
        return all(visited)

Complexity

Edge cases and common mistakes

• Forgetting to mark room 0 — if it is not marked, a key back to room 0 pushes it again (harmless but wasteful) and the final count may be off.
• Marking when popping instead of when pushing — a room can then be pushed many times. Marking on push keeps the work linear.
• Duplicate keys or a key to the current room — the visited check ignores them.
• Single room — with n = 1, the answer is true immediately.