Problem statement

There are n rooms labelled 0 through n - 1, all locked except room 0. Room i contains the keys listed in rooms[i], each opening one other room.

Starting in room 0, return true if you can visit every room.

Example 1

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

Example 2

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: Room 2 can never be opened.

Example 3

Input: rooms = [[]]
Output: true

Constraints

• 1 <= rooms.length <= 30
• 0 <= rooms[i][j] < rooms.length
• All keys within one room are distinct.

Hints for Keys and Rooms

1. Hint 1

   This is plain reachability from node 0 in a directed graph.

2. Hint 2

   DFS or BFS, marking rooms as you enter them so you never revisit one.

3. Hint 3

   The answer is whether the number of rooms reached equals the total.

How to solve Keys and Rooms

Reachability from node 0: DFS/BFS marking rooms as they are entered, then compare the count with n.

Approach

1. Mark room 0 seen and push it.
2. Pop a room, push every unseen key it holds (marking it).
3. Return visited == n.

Why it works

The rooms and keys form a directed graph; the set of rooms you can enter is exactly the set reachable from 0.

Complexity

• Time — O(rooms + keys)
• Space — O(rooms)

Pitfalls

• Mark a room when it is pushed, not when it is popped, to avoid duplicate pushes.

Reference solution

Python

def canVisitAllRooms(rooms) -> bool:
    seen = [False] * len(rooms)
    seen[0] = True
    stack = [0]
    visited = 1
    while stack:
        room = stack.pop()
        for key in rooms[room]:
            if not seen[key]:
                seen[key] = True
                visited += 1
                stack.append(key)
    return visited == len(rooms)

Java

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

C++

bool canVisitAllRooms(vector<vector<int>>& rooms) {
    int n = (int) rooms.size();
    vector<bool> seen(n, false);
    seen[0] = true;
    vector<int> stack;
    stack.push_back(0);
    int visited = 1;
    while (!stack.empty()) {
        int room = stack.back();
        stack.pop_back();
        for (int key : rooms[room]) {
            if (!seen[key]) {
                seen[key] = true;
                visited++;
                stack.push_back(key);
            }
        }
    }
    return visited == n;
}

JavaScript

var canVisitAllRooms = function(rooms) {
    const n = rooms.length;
    const seen = [];
    for (let i = 0; i < n; i++) seen.push(false);
    seen[0] = true;
    const stack = [0];
    let visited = 1;
    while (stack.length > 0) {
        const room = stack.pop();
        for (let i = 0; i < rooms[room].length; i++) {
            const key = rooms[room][i];
            if (!seen[key]) {
                seen[key] = true;
                visited++;
                stack.push(key);
            }
        }
    }
    return visited === n;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Implement Magic Dictionary Medium
• Design Add and Search Words Data Structure Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium