Keys and Rooms

Share

There are n rooms numbered 0 to n-1. Each room has keys to other rooms. You start in room 0. Can you visit all rooms?

Example 1
Input: [[1],[2],[3],[]] → Output: true
Example 2
Input: [[1,3],[3,0,1],[2],[0]] → Output: false

Solution Approach

BFS/DFS from room 0. Collect keys, visit newly accessible rooms. If all n rooms visited, return true.

  • Start with keys from room 0.
  • BFS: for each key in hand (unvisited room), visit it and collect its keys.
  • Mark visited as we go.
  • Return visited.size() == n.
Java
import java.util.*;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> visited = new HashSet<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0); visited.add(0);
        while (!stack.isEmpty()) {
            int room = stack.pop();
            for (int key : rooms.get(room)) {
                if (!visited.contains(key)) { visited.add(key); stack.push(key); }
            }
        }
        return visited.size() == rooms.size();
    }
}
  • Time Complexity: O(V+E)
  • Space Complexity: O(V)