841. Keys and Rooms
Explanation
To solve this problem, we can use a depth-first search (DFS) algorithm. We start by visiting room 0 and add its keys to a set of visited rooms. Then, we recursively visit all the rooms that can be unlocked with the keys obtained from the current room. We continue this process until we either visit all rooms or cannot unlock any more rooms. If we have visited all rooms by the end, we return true; otherwise, we return false.
Time Complexity: O(n + e), where n is the number of rooms and e is the total number of keys.
Space Complexity: O(n), where n is the number of rooms.
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Set<Integer> visited = new HashSet<>();
dfs(rooms, 0, visited);
return visited.size() == rooms.size();
}
private void dfs(List<List<Integer>> rooms, int room, Set<Integer> visited) {
visited.add(room);
for (int key : rooms.get(room)) {
if (!visited.contains(key)) {
dfs(rooms, key, visited);
}
}
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.