Solution: Keys and Rooms

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Keys and Rooms

Table of Contents

Contents are not accessible

Problem Statement

You are given n rooms labeled from 0 to n-1. Initially, you can only enter inside the room 0, and all other rooms are locked. However, you cannot enter a locked room without having its key.

Each room may contain a set of keys, each key opens a specific room. Each key has a number n on it, which opens up n<sup>th</sup> room starting from 0, 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. Otherwise, return false.

Examples

Example 1:

Input: rooms = [[1, 2], [1], [4, 3], [4], [3]]
Expected Output: true
Justification:
- Visit room 0 and get keys to rooms 1 and 2.
- Visit room 2 and get keys to rooms 3 and 4.

Example 2:

Input: rooms = [[1,2,3], [], [], []]
Expected Output: true
Justification: All keys are in room 0, so you can unlock all rooms immediately.

Example 3:

Input: rooms = [[3], [1], [2], [0]]
Expected Output: false
Justification: You can't visit rooms 1 and 2, as the keys for those rooms are in themselves.

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

To solve this problem, we can use a depth-first search (DFS) approach. The key idea is to start from room 0 and explore all reachable rooms by using the keys found in each room. We will use a set to keep track of visited rooms to avoid cycles and redundant checks.

This approach is effective because it systematically explores all possible paths starting from the initial room, ensuring that every accessible room is visited. If, after the DFS, all rooms have been visited, we can conclude that it's possible to visit all rooms; otherwise, it is not.

Step-by-step Algorithm

Initialize:
- Create a set called visited to store the indices of rooms that have been visited.
Define a DFS function:
- Define a function dfs(current) that takes the current room index as an argument.
Inside the DFS function:
1. Mark the current room as visited:
  - Add the current room to the visited set.
2. Explore each key in the current room:
  - Iterate over each key in rooms[current].
3. Check if the room corresponding to the key has been visited:
  - For each key:
    1. If the room corresponding to the key is not visited:
      - Recursively call dfs(key).
Start DFS from room 0:
- Call the dfs function with the initial room index 0.
Check if all rooms have been visited:
- After the DFS completes, check if the size of the visited set is equal to the number of rooms.
Return the result:
- Return true if all rooms have been visited, otherwise return false.

Algorithm Walkthrough

Given input: rooms = [[1, 2], [1], [4, 3], [4], [3]]

Start at room 0:
1. Initialize visited = {}.
2. Call dfs(0).
3. Inside dfs(0):
  - Mark room 0 as visited: visited = {0}.
  - Room 0 has keys [1, 2].
Visit room 1 (using key 1):
1. Call dfs(1).
2. Inside dfs(1):
  - Mark room 1 as visited: visited = {0, 1}.
  - Room 1 has keys [1].
  - Key 1 leads to room 1, which is already visited.
3. Return to dfs(0).
Visit room 2 (using key 2):
1. Call dfs(2).
2. Inside dfs(2):
  - Mark room 2 as visited: visited = {0, 1, 2}.
  - Room 2 has keys [4, 3].
Visit room 4 (using key 4):
1. Call dfs(4).
2. Inside dfs(4):
  - Mark room 4 as visited: visited = {0, 1, 2, 4}.
  - Room 4 has keys [3].
Visit room 3 (using key 3):
1. Call dfs(3).
2. Inside dfs(3):
  - Mark room 3 as visited: visited = {0, 1, 2, 3, 4}.
  - Room 3 has keys [4].
  - Key 4 leads to room 4, which is already visited.
3. Return to dfs(4) and then to dfs(2).
Completion:
1. All keys in room 2 have been processed.
2. Return to dfs(0).
Final check:
1. The size of visited is 5, which is equal to the number of rooms.
Result:
1. Return true because all rooms have been visited.

Code

Python3

. . . .

Complexity Analysis

Time Complexity: The time complexity of this algorithm is $O(n + e)$ , where n is the number of rooms and e is the total number of keys. This is because we visit each room once and iterate over all keys once.
Space Complexity: The space complexity is $O(n)$ , where n is the number of rooms. This is due to the recursion stack in the DFS and the space needed to store the visited rooms.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible