Keys and Rooms

LeetCode 841: Keys and Rooms Solution & Explanation

Problem Overview

TL;DR: The optimal solution treats the rooms and keys as a directed graph and uses Depth-First Search (DFS) to determine if the connected component containing room 0 includes all $n$ nodes.

In the LeetCode 841 problem "Keys and Rooms," you are given a set of rooms. Room 0 is unlocked, and every room contains a list of keys that open other specific rooms. The objective is to determine if it is possible to visit every single room starting from room 0. This is a classic reachability problem where we must verify if the graph is fully connected from a specific source node.

Brute Force Approach for Keys and Rooms

A naive approach to solving Keys and Rooms might involve an iterative simulation that repeatedly scans the list of rooms to see if any new keys have been acquired.

1. Maintain a set of collected_keys (initially {0}) and a set of visited_rooms.
2. Loop through all rooms from 0 to n-1.
3. If we have the key for room i but haven't "processed" it yet, enter the room, add all its keys to collected_keys, and mark it as processed.
4. Repeat step 2 and 3 until a full pass over the rooms results in no new keys being found.
5. Check if the number of visited rooms equals n.

Why this fails

While this logic eventually works, it is highly inefficient. In the worst case, discovering one new key might require scanning the entire rooms array again.

• Time Complexity: $O(N^2)$ or worse, depending on the specific implementation of the loop, where $N$ is the number of rooms.
• Inefficiency: This approach does not follow the natural structure of the data (a graph). It treats the connections as a flat list to be polled, leading to redundant checks.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

We will implement the Depth-First Search (DFS) strategy to solve this.

1. State Management: Create a boolean array or hash set called visited to keep track of unlocked rooms. Initialize it with false (or empty), and mark room 0 as visited immediately.
2. Traversal: Initiate a DFS function starting at node 0.
3. Recursive Logic:
   • For the current room, iterate through every key found in that room.
   • For each key (which corresponds to a neighbor node), check if that room has already been visited.
   • If it has not been visited, mark it as visited and recursively call the DFS function on that room.
4. Constraint Enforcement: The visited check enforces the boundary that we never process a node twice, ensuring linear time complexity.
5. Final Verification: After the DFS traversal completes, count the number of true entries in visited. If the count equals n, all rooms are reachable.

Execution Flow

1. Initialization:

   • n = 4.
   • rooms = [[1], [2], [3], []].
   • visited = {0}.
   • count = 1.
   • Call dfs(0).

2. Step 1 (Room 0):

   • Current node: 0.
   • Keys found: [1].
   • Neighbor 1 is not in visited.
   • Add 1 to visited. Increment count to 2.
   • Recurse: Call dfs(1).

3. Step 2 (Room 1):

   • Current node: 1.
   • Keys found: [2].
   • Neighbor 2 is not in visited.
   • Add 2 to visited. Increment count to 3.
   • Recurse: Call dfs(2).

4. Step 3 (Room 2):

   • Current node: 2.
   • Keys found: [3].
   • Neighbor 3 is not in visited.
   • Add 3 to visited. Increment count to 4.
   • Recurse: Call dfs(3).

5. Step 4 (Room 3):

   • Current node: 3.
   • Keys found: [].
   • No neighbors to visit.
   • Return from dfs(3).

6. Backtracking:

   • Control returns to dfs(2), then dfs(1), then dfs(0).
   • No other unvisited neighbors exist.

7. Final Check:

   • count (4) equals n (4).
   • Return true.

Proof of Correctness

The algorithm is correct because DFS exhaustively explores the connected component of the graph starting from the source node.

1. Reachability: If a path exists from Room 0 to Room $k$, the recursive nature of DFS guarantees that we will eventually traverse the edge leading to $k$.
2. Termination: Since there are a finite number of rooms ($n$) and we only recurse into unvisited rooms, the algorithm is guaranteed to terminate.
3. Completeness: By counting the size of the visited set after the traversal finishes, we strictly measure the size of the reachable subgraph. If this size matches the total number of nodes, the graph is fully connected from the source.

Pattern Reuse Notes

The Graph DFS - Connected Components pattern used in this solution is fundamental to many graph problems.

• LeetCode 200: Number of Islands: Instead of checking one component starting at 0, you iterate through the entire grid and launch a DFS for every unvisited "land" cell to count total components.
• LeetCode 547: Number of Provinces: Identical logic. The input is an adjacency matrix, but the goal is to count how many disconnected components exist in the graph.
• LeetCode 130: Surrounded Regions: Uses DFS starting from boundary 'O's to mark the "safe" connected component, then flips the rest.
• LeetCode 417: Pacific Atlantic Water Flow: Runs two separate DFS passes (one from the Pacific ocean edges, one from Atlantic) to find the intersection of reachable nodes.

Reference Implementation

C++ Solution for LeetCode 841

1class Solution {
2public:
3    void dfs(int node, const vector<vector<int>>& rooms, vector<bool>& visited) {
4        // Mark the current node as visited
5        visited[node] = true;
6        
7        // Iterate through all keys (edges) found in this room
8        for (int neighbor : rooms[node]) {
9            // Only recurse if the neighbor hasn't been visited yet
10            if (!visited[neighbor]) {
11                dfs(neighbor, rooms, visited);
12            }
13        }
14    }
15
16    bool canVisitAllRooms(vector<vector<int>>& rooms) {
17        int n = rooms.size();
18        vector<bool> visited(n, false);
19        
20        // Start DFS from room 0
21        dfs(0, rooms, visited);
22        
23        // Check if all rooms were marked as visited
24        for (bool v : visited) {
25            if (!v) return false;
26        }
27        return true;
28    }
29};

Java Solution for LeetCode 841

1class Solution {
2    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
3        int n = rooms.size();
4        boolean[] visited = new boolean[n];
5        
6        // Start DFS from room 0
7        dfs(0, rooms, visited);
8        
9        // Check if all rooms were visited
10        for (boolean v : visited) {
11            if (!v) return false;
12        }
13        return true;
14    }
15    
16    private void dfs(int node, List<List<Integer>> rooms, boolean[] visited) {
17        // Mark current node as visited
18        visited[node] = true;
19        
20        // Iterate through all keys in the current room
21        for (int key : rooms.get(node)) {
22            // Only traverse if the room hasn't been visited
23            if (!visited[key]) {
24                dfs(key, rooms, visited);
25            }
26        }
27    }
28}

Python Solution for LeetCode 841

1class Solution:
2    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
3        visited = set()
4        
5        def dfs(node):
6            # Mark the current node as visited
7            visited.add(node)
8            
9            # Iterate through all keys in the current room
10            for key in rooms[node]:
11                # Only recurse if the room is not in visited set
12                if key not in visited:
13                    dfs(key)
14        
15        # Start DFS traversal from room 0
16        dfs(0)
17        
18        # Return true if the number of visited rooms equals total rooms
19        return len(visited) == len(rooms)