LeetCode 841: Keys and Rooms Solution
Master LeetCode problem 841 (Keys and Rooms), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
841. Keys and Rooms
Problem Explanation
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.
Solution Code
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);
}
}
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 841 (Keys and Rooms)?
This page provides optimized solutions for LeetCode problem 841 (Keys and Rooms) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 841 (Keys and Rooms)?
The time complexity for LeetCode 841 (Keys and Rooms) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 841 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 841 in Java, C++, or Python.