{x}
blog image

Keys and Rooms

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.

Solution Explanation for LeetCode 841: Keys and Rooms

This problem asks whether it's possible to visit all rooms given a set of keys found in each room. The rooms are represented as a graph where rooms are nodes and keys are edges. We can solve this using either Depth-First Search (DFS) or Breadth-First Search (BFS).

Core Idea: Both DFS and BFS systematically explore the graph, starting from room 0. They mark visited rooms to avoid cycles and ensure all reachable rooms are explored. If the number of visited rooms equals the total number of rooms, all rooms are accessible.

1. Depth-First Search (DFS):

  • Approach: The DFS algorithm recursively explores the graph. It starts at room 0 and explores as deeply as possible along each branch before backtracking. A visited set (or array) tracks visited rooms.

  • Time Complexity: O(V + E), where V is the number of vertices (rooms) and E is the number of edges (keys). We visit each room and each key at most once.

  • Space Complexity: O(V) in the worst case, due to the recursive call stack (depth of recursion could be V in a worst-case scenario – a very deep, linked graph). The visited set also contributes to the space complexity.

2. Breadth-First Search (BFS):

  • Approach: BFS explores the graph level by level. It uses a queue to store rooms to be visited. It starts by adding room 0 to the queue. It then repeatedly dequeues a room, marks it as visited, and adds its adjacent (reachable) rooms to the queue.

  • Time Complexity: O(V + E). Similar to DFS, we visit each room and each key at most once.

  • Space Complexity: O(V) in the worst case. The queue can hold all the rooms in the worst-case scenario (a completely connected graph).

Code Examples (Python):

DFS:

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        visited[0] = True  # Mark room 0 as visited initially
        count = 1          # Initialize count of visited rooms to 1 (for room 0)
 
        def dfs(room):
            nonlocal count  # Access the outer count variable
            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    count += 1
                    dfs(key)
 
        dfs(0)
        return count == n

BFS:

from collections import deque
 
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        visited[0] = True
        queue = deque([0])
        count = 1
 
        while queue:
            room = queue.popleft()
            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    count += 1
                    queue.append(key)
 
        return count == n

Both solutions achieve the same result. The choice between DFS and BFS often depends on specific problem characteristics; in this case, both are equally efficient. The BFS implementation might be slightly preferable in some cases because it uses iterative approach, avoiding potential stack overflow issues that could arise with very deep recursive calls in DFS (though unlikely with the problem constraints). However, for this particular problem, the difference is minimal.