Problem 9 - Keys and Rooms

Explore our archive for previous posts.

Question

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.

Example 1:

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:

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.

Constraints:

• n == rooms.length

• 2 <= n <= 1000

• 0 <= rooms[i].length <= 1000

• 1 <= sum(rooms[i].length) <= 3000

• 0 <= rooms[i][j] < n

• All the values of rooms[i] are unique.

Approach

This solution uses a boolean array visited to track the visited rooms. We start with the first room (room 0) and perform depth first search (DFS) by recursively visiting its neighboring rooms. If we encounter a room that has not been visited, we mark it as visited and recursively call the DFS function on that room. We continue this process until all reachable rooms have been visited.

After the DFS traversal, we check if all the rooms have been visited. If there is any room that remains unvisited, we return false; otherwise, we return true.

Solution

Solve it here

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int numRooms = rooms.size();
        boolean[] visited = new boolean[numRooms]; // Track visited rooms
        visited[0] = true; // Mark the first room as visited

        // Perform DFS starting from the first room
        dfs(rooms, 0, visited);

        // Check if all rooms have been visited
        for (boolean roomVisited : visited) {
            if (!roomVisited) {
                return false;
            }
        }

        return true;
    }

    private void dfs(List<List<Integer>> rooms, int currRoom, boolean[] visited) {
        List<Integer> keys = rooms.get(currRoom);

        // Visit all the unvisited neighboring rooms
        for (int key : keys) {
            if (!visited[key]) {
                visited[key] = true; // Mark the room as visited
                dfs(rooms, key, visited); // Recursively visit the neighboring room
            }
        }
    }
}

Time and space complexity

Time Complexity: The time complexity of the above solution is O(N + E), where N is the number of rooms and E is the total number of keys across all rooms. This is because we visit each room and its corresponding keys exactly once.

Space Complexity: The space complexity of the solution is O(N), where N is the number of rooms. This is because we use a boolean array of size N to track visited rooms. Additionally, during the recursive DFS traversal, the maximum depth of the call stack is also proportional to N.