Problem

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:
rooms = [[1],[2],[3],[]]
Output:
 true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

Example 2:

1
2
3
4
5

Input:
rooms = [[1,3],[3,0,1],[2],[0]]
Output:
 false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Solution

Method 1 – BFS Traversal

Intuition

We treat each room as a node and each key as an edge to another node. Starting from room 0, we use BFS to visit all rooms we can reach using the keys found. If all rooms are visited, return true; otherwise, false.

Approach

  1. Initialize a queue with room 0 and a visited set.
  2. While the queue is not empty:
    • Pop a room from the queue.
    • For each key in the room, if the room is not visited, add it to the queue and mark as visited.
  3. After traversal, check if all rooms are visited.

Code

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] vis = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        vis[0] = true;
        int cnt = 1;
        while (!q.isEmpty()) {
            int room = q.poll();
            for (int key : rooms.get(room)) {
                if (!vis[key]) {
                    vis[key] = true;
                    q.offer(key);
                    cnt++;
                }
            }
        }
        return cnt == n;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the number of rooms and m is the total number of keys.
  • 🧺 Space complexity: O(n), for the visited array and queue.

Method 2 – DFS Traversal

Intuition

We can also use DFS to visit all rooms starting from room 0, recursively visiting rooms using the keys found. If all rooms are visited, return true; otherwise, false.

Approach

  1. Initialize a visited array.
  2. Define a recursive DFS function to visit rooms.
  3. Start DFS from room 0.
  4. After traversal, check if all rooms are visited.

Code

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] vis = new boolean[n];
        dfs(0, rooms, vis);
        for (boolean v : vis) if (!v) return false;
        return true;
    }
    void dfs(int room, List<List<Integer>> rooms, boolean[] vis) {
        vis[room] = true;
        for (int key : rooms.get(room)) {
            if (!vis[key]) dfs(key, rooms, vis);
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the number of rooms and m is the total number of keys.
  • 🧺 Space complexity: O(n), for the visited array and recursion stack.