Keys and Rooms

Problem Statement

The objective is to determine whether all the rooms in a sequence can be visited starting from room 0, which is initially unlocked. Rooms from 1 to n-1 are locked. Access to each room is governed by a set of keys one finds in another room, specifically in an array rooms, such that rooms[i] contains keys that can unlock other rooms. You can only move to another room if you possess the respective key which you pick up from the rooms visited. The question then is, given the distribution of keys in the array rooms, whether it is possible to visit every room by collecting and using the keys found.

Examples

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 and Intuition

Logical Steps for the Approach

1. Start with Room 0, initializing it as visited and gather all available keys.
2. Employ a traversal mechanism, such as Breadth-First Search (BFS) or Depth-First Search (DFS), to systematically visit rooms as keys get discovered.
3. Maintain a record of visited rooms to avoid redundant checks and recursive loops.
4. Continue visiting rooms and collecting keys until no new rooms can be accessed.
5. At the end of the traversal, if all rooms have been marked as visited, return true.
6. If some rooms remain unvisited after exhausting all accessible keys, return false.

Key Constraints to Consider

• The organization and connectivity provided by the keys inside the rooms is critical. If a key to a room lies inside the same room (and not available through any other), that room will remain locked forever, making the answer false.
• The problem involves navigating through indirect relations and dependencies, echoing a graph traversal problem where rooms are nodes and keys act as edges connecting these nodes. Thus, analyzing it as a graph problem can be computationally efficient.
• Consideration of upper limits of n (number of rooms) and total number of keys can guide whether to use more space or time-efficient algorithms.

The problem essentially tests the ability to traverse all connected components of a dynamically revealed graph where the action of visiting a node reveals further edges.

Solutions

class RoomVisitor {
    public boolean exploreAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];
        visited[0] = true;
        Stack<Integer> todoStack = new Stack();
        todoStack.push(0);

        while (!todoStack.isEmpty()) {
            int currentRoom = todoStack.pop();
            for (int neighbor: rooms.get(currentRoom)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    todoStack.push(neighbor);
                }
            }
        }

        for (boolean roomVisited: visited)
            if (!roomVisited) return false;
        return true;
    }
}