0% completed
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 rooms1
and2
. - Visit room
2
and get keys to rooms3
and4
.
- Visit room
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
and2
, 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.
- Create a set called
-
Define a DFS function:
- Define a function
dfs(current)
that takes the current room index as an argument.
- Define a function
-
Inside the DFS function:
- Mark the current room as visited:
- Add the
current
room to thevisited
set.
- Add the
- Explore each key in the current room:
- Iterate over each key in
rooms[current]
.
- Iterate over each key in
- Check if the room corresponding to the key has been visited:
- For each key:
- If the room corresponding to the key is not visited:
- Recursively call
dfs(key)
.
- Recursively call
- If the room corresponding to the key is not visited:
- For each key:
- Mark the current room as visited:
-
Start DFS from room 0:
- Call the
dfs
function with the initial room index0
.
- Call the
-
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.
- After the DFS completes, check if the size of the
-
Return the result:
- Return
true
if all rooms have been visited, otherwise returnfalse
.
- Return
Algorithm Walkthrough
Given input: rooms = [[1, 2], [1], [4, 3], [4], [3]]
-
Start at room 0:
- Initialize
visited = {}
. - Call
dfs(0)
. - Inside
dfs(0)
:- Mark room
0
as visited:visited = {0}
. - Room
0
has keys[1, 2]
.
- Mark room
- Initialize
-
Visit room 1 (using key
1
):- Call
dfs(1)
. - Inside
dfs(1)
:- Mark room
1
as visited:visited = {0, 1}
. - Room
1
has keys[1]
. - Key
1
leads to room1
, which is already visited.
- Mark room
- Return to
dfs(0)
.
- Call
-
Visit room 2 (using key
2
):- Call
dfs(2)
. - Inside
dfs(2)
:- Mark room
2
as visited:visited = {0, 1, 2}
. - Room
2
has keys[4, 3]
.
- Mark room
- Call
-
Visit room 4 (using key
4
):- Call
dfs(4)
. - Inside
dfs(4)
:- Mark room
4
as visited:visited = {0, 1, 2, 4}
. - Room
4
has keys[3]
.
- Mark room
- Call
-
Visit room 3 (using key
3
):- Call
dfs(3)
. - Inside
dfs(3)
:- Mark room
3
as visited:visited = {0, 1, 2, 3, 4}
. - Room
3
has keys[4]
. - Key
4
leads to room4
, which is already visited.
- Mark room
- Return to
dfs(4)
and then todfs(2)
.
- Call
-
Completion:
- All keys in room
2
have been processed. - Return to
dfs(0)
.
- All keys in room
-
Final check:
- The size of
visited
is5
, which is equal to the number of rooms.
- The size of
-
Result:
- Return
true
because all rooms have been visited.
- Return
Code
Complexity Analysis
- Time Complexity: The time complexity of this algorithm is O(n + e), where
n
is the number of rooms ande
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.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible