Keys and Rooms

Problem

Rooms 0..n-1 are locked except room 0. rooms[i] lists keys you find in room i. Return true iff you can visit every room.

Constraints

• 1 ≤ rooms.length ≤ 1000

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def canVisitAllRooms(self, rooms):
        seen = {0}
        stack = [0]
        while stack:
            for key in rooms[stack.pop()]:
                if key not in seen:
                    seen.add(key)
                    stack.append(key)
        return len(seen) == len(rooms)

Java

import java.util.*;
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        // BFS from room 0 with a visited array — plain reachability.
        boolean[] seen = new boolean[rooms.size()];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);
        seen[0] = true;
        int visited = 1;
        while (!q.isEmpty()) {
            int r = q.poll();
            for (int k : rooms.get(r))
                if (!seen[k]) { seen[k] = true; visited++; q.offer(k); }
        }
        return visited == rooms.size();

        // DFS (recursive or an explicit stack) works identically here —
        // reachability doesn't care about visit order.
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.