Code Implementation

class Solution:
    def canVisitAllRooms(self, rooms):
        visited = set()
        def dfs(room):
            visited.add(room)
            for key in rooms[room]:
                if key not in visited:
                    dfs(key)
        dfs(0)
        return len(visited) == len(rooms)
      

class Solution {
public:
    void dfs(int room, vector<vector<int>>& rooms, vector<bool>& visited) {
        visited[room] = true;
        for (int key : rooms[room]) {
            if (!visited[key]) {
                dfs(key, rooms, visited);
            }
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<bool> visited(n, false);
        dfs(0, rooms, visited);
        for (bool v : visited) {
            if (!v) return false;
        }
        return true;
    }
};
      

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

var canVisitAllRooms = function(rooms) {
    let visited = new Set();
    function dfs(room) {
        visited.add(room);
        for (let key of rooms[room]) {
            if (!visited.has(key)) {
                dfs(key);
            }
        }
    }
    dfs(0);
    return visited.size === rooms.length;
};
      

Problem Description

You are given a list of rooms, where each room is represented as a list of keys. Each key is an integer corresponding to another room's index. All rooms are locked except for room 0, which is always unlocked. You start in room 0 and can use any keys you find to unlock other rooms. Your task is to determine if you can visit every room by collecting and using keys as you go.

• Each room may contain zero or more keys.
• You may only use the keys you collect as you visit rooms; you cannot "guess" or "force" a door.
• There is only one set of rooms and keys; you cannot reuse a key for the same room multiple times.
• Your output should be true if you can visit every room, and false otherwise.

Thought Process

At first glance, this problem seems similar to exploring a maze or traversing a network: you start in one place and can move to others if you have the right keys. The brute-force approach would be to try every possible sequence of key uses, but that quickly becomes infeasible as the number of rooms grows.

A more efficient way is to recognize that this is essentially a graph traversal problem, where each room is a node and keys represent edges to other nodes. We want to see if we can reach all nodes (rooms) starting from node 0. This is a classic use case for Depth-First Search (DFS) or Breadth-First Search (BFS).

The key insight is: if we can visit every room by following the keys, then we've "connected" the whole graph starting from room 0. If any room remains unvisited, we must return false.

Solution Approach

• Model the problem as a graph: Each room is a node, and each key in a room is a directed edge to another room.
• Use DFS traversal: Start from room 0, mark it as visited, and for each key in the current room, recursively visit the corresponding room if it hasn't been visited yet.
• Track visited rooms: Use a visited set (or array) to record which rooms have been entered.
• Termination condition: After traversal, check if the number of visited rooms equals the total number of rooms. If yes, return true; otherwise, return false.
• Why DFS? DFS is simple to implement recursively and efficiently explores all reachable rooms from the starting point. BFS is also possible, but DFS is concise for this use case.

Example Walkthrough

Example Input: rooms = [[1],[2],[3],[]]

1. Start in room 0 (unlocked). Room 0 contains key 1.
2. Use key 1 to enter room 1. Room 1 contains key 2.
3. Use key 2 to enter room 2. Room 2 contains key 3.
4. Use key 3 to enter room 3. Room 3 contains no keys.
5. All rooms (0, 1, 2, 3) have been visited. Return true.

Example Input: rooms = [[1,3],[3,0,1],[2],[0]]

1. Start in room 0 (unlocked). Room 0 contains keys 1 and 3.
2. Use key 1 to enter room 1. Room 1 contains keys 3, 0, and 1.
3. Use key 3 to enter room 3. Room 3 contains key 0.
4. Use key 2 (from room 2) to enter room 2. But unless you have a key to room 2, you cannot enter it. Since no key to room 2 is found, you cannot visit all rooms. Return false.

Time and Space Complexity

• Brute-force approach: Would try all possible sequences of key usage, leading to exponential time complexity (much worse than O(n)).
• Optimized DFS/BFS approach:
  • Time Complexity: O(N + E), where N is the number of rooms and E is the total number of keys (edges). Each room and each key is visited at most once.
  • Space Complexity: O(N) for the visited set or array and the call stack (in DFS).

Summary

The "Keys and Rooms" problem is a classic example of graph traversal. By modeling rooms as nodes and keys as connections, we efficiently determine reachability using DFS or BFS. The key insight is that visiting all rooms is equivalent to traversing all connected nodes in a graph. This approach is efficient, elegant, and scales well even for large inputs.