Keys and Rooms solution and explanation
Google
Infosys
9 more videos on this problem
LeetCode Keys and Rooms Solution Explained - JavaNick White · 7:05 · 22K views
Keys and Rooms | Live Coding with Explanation | Leetcode - 841Algorithms Made Easy · 6:24 · 5K views
Keys and Rooms - LeetCode 841 PythonDeepti Talesra · 5:20 · 4K views
Leetcode - Keys and Rooms (Python)Timothy H Chang · 3:19 · 3K views
Keys And Rooms - LeetCode 841 - JavaScriptAlgoJS · 4:53 · 1K views
LeetCode 841. Keys and Rooms - PythonHelmyCodeCamp · 7:46 · 1K views
LeetCode 841| Keys and Rooms | DFS (Java Solution with Explanation)The Tech Granth · 8:43 · 359 views
Leetcode 841 - Keys and Rooms (JAVA, Solution Explain!)LC Bear · 8:20 · 338 views
Keys and Rooms | LeetCode 841 | Coders CampCoders Camp · 5:54 · 283 views
841. Keys and Rooms | LEETCODE MEDIUM | BFScode Explainer · 5:28 · 260 views
The problem
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.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < n- All the values of
rooms[i]are unique.
Approach overview
Problem Overview: You start in room 0. Each room may contain keys that unlock other rooms. The task is to determine whether you can visit every room by collecting and using these keys. Conceptually, each room is a node in a graph and each key represents a directed edge to another room.
Approach 1: Depth-First Search (DFS) (Time: O(n + e), Space: O(n))
Treat the input as a graph where room i has edges to the rooms listed in rooms[i]. Start a DFS from room 0. Every time you enter a room, mark it as visited and recursively explore all rooms whose keys you find there. A visited set or boolean array prevents revisiting rooms and avoids infinite cycles. After traversal finishes, check whether the number of visited rooms equals n. This approach works well because DFS naturally follows chains of keys deep into the graph before backtracking.
The key insight: the problem is simply checking whether all nodes are reachable from node 0. DFS efficiently explores reachability in graphs while maintaining O(n + e) time where n is the number of rooms and e is the total number of keys.
DFS is commonly used in graph traversal problems, especially when exploring connected components or reachability. If you want to review the concept, see Depth-First Search and Graph.
Approach 2: Breadth-First Search (BFS) (Time: O(n + e), Space: O(n))
BFS solves the same reachability problem but explores rooms level by level. Use a queue starting with room 0. Dequeue a room, mark it visited, and enqueue every new room whose key appears inside it. Each room is processed once, and each key is examined once, giving O(n + e) time complexity.
The difference from DFS is traversal order. BFS spreads outward from the starting room rather than diving deep first. In practice both approaches perform similarly for this problem. BFS may feel more intuitive if you think of unlocking rooms layer by layer.
BFS is another core traversal technique in graph problems. See Breadth-First Search for a deeper explanation.
Recommended for interviews: Either DFS or BFS is acceptable since both achieve optimal O(n + e) time and O(n) space. DFS is often slightly shorter to implement with recursion, while BFS demonstrates comfort with queue-based graph traversal. Interviewers mainly look for the recognition that rooms and keys form a graph reachability problem.
Approach 1: Depth-First Search (DFS) Approach
The idea is to use Depth-First Search (DFS) to explore all reachable rooms starting from room 0. This can be implemented either recursively or iteratively with a stack. We maintain a set of visited rooms and attempt to visit all rooms that we have keys for, recursively adding rooms to the visited set as we access them. The process continues until no new rooms can be explored.
def canVisitAllRooms(rooms):
visited = set()
def dfs(room):
if room not in visited:
visited.add(room)
for key in rooms[room]:
dfs(key)
dfs(0)
return len(visited) == len(rooms)import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Set<Integer> visited = new HashSet<>();
dfs(rooms, visited, 0);
return visited.size() == rooms.size();
}
private void dfs(List<List<Integer>> rooms, Set<Integer> visited, int room) {
if (!visited.contains(room)) {
visited.add(room);
for (int key : rooms.get(room)) {
dfs(rooms, visited, key);
}
}
}
}#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
unordered_set<int> visited;
dfs(rooms, visited, 0);
return visited.size() == rooms.size();
}
private:
void dfs(const vector<vector<int>>& rooms, unordered_set<int>& visited, int room) {
if (visited.find(room) == visited.end()) {
visited.insert(room);
for (int key : rooms[room]) {
dfs(rooms, visited, key);
}
}
}
};var canVisitAllRooms = function(rooms) {
const visited = new Set();
const dfs = (room) => {
if (!visited.has(room)) {
visited.add(room);
for (const key of rooms[room]) {
dfs(key);
}
}
};
dfs(0);
return visited.size === rooms.length;
};#include <stdbool.h>
#include <stdlib.h>
void dfs(int** rooms, int* roomsColSize, bool* visited, int room) {
if (!visited[room]) {
visited[room] = true;
for (int i = 0; i < roomsColSize[room]; i++) {
dfs(rooms, roomsColSize, visited, rooms[room][i]);
}
}
}
bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize) {
bool* visited = (bool*)calloc(roomsSize, sizeof(bool));
dfs(rooms, roomsColSize, visited, 0);
for (int i = 0; i < roomsSize; i++) {
if (!visited[i]) {
free(visited);
return false;
}
}
free(visited);
return true;
}using System.Collections.Generic;
public class Solution {
public bool CanVisitAllRooms(IList<IList<int>> rooms) {
var visited = new HashSet<int>();
DFS(rooms, visited, 0);
return visited.Count == rooms.Count;
}
private void DFS(IList<IList<int>> rooms, HashSet<int> visited, int room) {
if (!visited.Contains(room)) {
visited.Add(room);
foreach (var key in rooms[room]) {
DFS(rooms, visited, key);
}
}
}
}This solution defines a dfs function to explore rooms recursively. The visited set is used to keep track of rooms that have already been visited to avoid re-processing. The algorithm starts DFS from room 0, recursively visiting each room for which we have a key until no new rooms can be visited.
Space Complexity: O(N) for the recursion stack and the visited set.
Approach 2: Breadth-First Search (BFS) Approach
Instead of using DFS, we can also use Breadth-First Search (BFS) to explore the rooms iteratively. We use a queue to maintain the rooms to be visited next. Initially, room 0 is added to the queue. As we visit each room, we add all the keys found in that room to the queue, provided we haven't visited the corresponding rooms yet. This approach ensures a layer-wise exploration similar to BFS.
from collections import deque
def canVisitAllRooms(rooms):
visited = set()
queue = deque([0])
visited.add(0)
while queue:
room = queue.popleft()
for key in rooms[room]:
if key not in visited:
visited.add(key)
queue.append(key)
return len(visited) == len(rooms)import java.util.*;
public class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
visited.add(0);
while (!queue.isEmpty()) {
int room = queue.poll();
for (int key : rooms.get(room)) {
if (!visited.contains(key)) {
visited.add(key);
queue.add(key);
}
}
}
return visited.size() == rooms.size();
}
}#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
unordered_set<int> visited;
queue<int> q;
q.push(0);
visited.insert(0);
while (!q.empty()) {
int room = q.front();
q.pop();
for (int key : rooms[room]) {
if (visited.find(key) == visited.end()) {
visited.insert(key);
q.push(key);
}
}
}
return visited.size() == rooms.size();
}
};var canVisitAllRooms = function(rooms) {
const visited = new Set();
const queue = [0];
visited.add(0);
while (queue.length > 0) {
const room = queue.shift();
for (const key of rooms[room]) {
if (!visited.has(key)) {
visited.add(key);
queue.push(key);
}
}
}
return visited.size === rooms.length;
};#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
void enqueue(int* queue, int* end, int room) {
queue[*end] = room;
(*end)++;
}
int dequeue(int* queue, int* start) {
return queue[(*start)++];
}
bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize) {
bool* visited = (bool*)calloc(roomsSize, sizeof(bool));
int* queue = (int*)malloc(roomsSize * sizeof(int));
int start = 0, end = 0;
enqueue(queue, &end, 0);
visited[0] = true;
while (start < end) {
int room = dequeue(queue, &start);
for (int i = 0; i < roomsColSize[room]; i++) {
int key = rooms[room][i];
if (!visited[key]) {
enqueue(queue, &end, key);
visited[key] = true;
}
}
}
for (int i = 0; i < roomsSize; i++) {
if (!visited[i]) {
free(queue);
free(visited);
return false;
}
}
free(queue);
free(visited);
return true;
}using System.Collections.Generic;
public class Solution {
public bool CanVisitAllRooms(IList<IList<int>> rooms) {
var visited = new HashSet<int>();
var queue = new Queue<int>();
queue.Enqueue(0);
visited.Add(0);
while (queue.Count > 0) {
int room = queue.Dequeue();
foreach (var key in rooms[room]) {
if (!visited.Contains(key)) {
visited.Add(key);
queue.Enqueue(key);
}
}
}
return visited.Count == rooms.Count;
}
}In this Python BFS implementation, we utilize a deque as a queue. Initially, room 0 is added to the queue and visited set. We process each room in the queue by adding unvisited rooms (for which we have keys) to the visited set and queue. We continue this until the queue is empty and then check if all rooms have been visited.
Space Complexity: O(N) for the queue and visited set.
Approach 3: Depth-First Search (DFS)
We can use the Depth-First Search (DFS) method to traverse the entire graph, count the number of reachable nodes, and use an array vis to mark whether the current node has been visited to prevent repeated visits.
Finally, we count the number of visited nodes. If it is the same as the total number of nodes, it means that all nodes can be visited; otherwise, there are nodes that cannot be reached.
The time complexity is O(n + m), and the space complexity is O(n), where n is the number of nodes, and m is the number of edges.
function canVisitAllRooms(rooms: number[][]): boolean {
const n = rooms.length;
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number) => {
if (vis[i]) {
return;
}
vis[i] = true;
for (const j of rooms[i]) {
dfs(j);
}
};
dfs(0);
return vis.every(v => v);
}func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
cnt := 0
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if vis[i] {
return
}
vis[i] = true
cnt++
for _, j := range rooms[i] {
dfs(j)
}
}
dfs(0)
return cnt == n
}impl Solution {
pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
let n = rooms.len();
let mut is_open = vec![false; n];
let mut keys = vec![0];
while !keys.is_empty() {
let i = keys.pop().unwrap();
if is_open[i] {
continue;
}
is_open[i] = true;
rooms[i].iter().for_each(|&key| keys.push(key as usize));
}
is_open.iter().all(|&v| v)
}
}Approach 4: BFS
We can also use the Breadth-First Search (BFS) method to traverse the entire graph. We use a hash table or an array vis to mark whether the current node has been visited to prevent repeated visits.
Specifically, we define a queue q, initially put node 0 into the queue, and then continuously traverse the queue. Each time we take out the front node i of the queue, if i has been visited, we skip it directly; otherwise, we mark it as visited, and then add the nodes that i can reach to the queue.
Finally, we count the number of visited nodes. If it is the same as the total number of nodes, it means that all nodes can be visited; otherwise, it means that there are unreachable nodes.
The time complexity is O(n + m), and the space complexity is O(n). Where n is the number of nodes, and m is the number of edges.
function canVisitAllRooms(rooms: number[][]): boolean {
const vis = new Set<number>();
const q: number[] = [0];
while (q.length) {
const i = q.pop()!;
if (vis.has(i)) {
continue;
}
vis.add(i);
q.push(...rooms[i]);
}
return vis.size == rooms.length;
}func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
vis := make([]bool, n)
cnt := 0
q := []int{0}
for len(q) > 0 {
i := q[0]
q = q[1:]
if vis[i] {
continue
}
vis[i] = true
cnt++
for _, j := range rooms[i] {
q = append(q, j)
}
}
return cnt == n
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Approach | Time Complexity: O(N + E), where N is the number of rooms and E is the total number of keys. Space Complexity: O(N) for the recursion stack and the visited set. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(N + E), where N is the number of rooms and E is the total number of keys. Space Complexity: O(N) for the queue and visited set. |
| Depth-First Search (DFS) | – |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(n + e) | O(n) | Great for recursive exploration of graph reachability and concise implementations. |
| Breadth-First Search (BFS) | O(n + e) | O(n) | Useful when exploring nodes level-by-level using a queue. |
Frequently asked questions
Is Keys and Rooms easy or hard?
Keys and Rooms is considered a Medium difficulty problem. The logic is straightforward once you recognize it as a graph reachability problem, but beginners may struggle if they have not practiced DFS or BFS traversal patterns.
Keys and Rooms Python/Java solution
Most solutions implement DFS or BFS. Python often uses recursion with a visited set, while Java typically uses either recursion or a queue with a boolean array. Both implementations run in O(n + e) time and O(n) space.
How to solve Keys and Rooms in O(n)?
Model the problem as a graph traversal and start from room 0. Use DFS recursion or a BFS queue while tracking visited rooms with a boolean array or set. Continue exploring rooms whose keys you discover until traversal finishes, then verify that all rooms were visited.
What is the best approach for Keys and Rooms?
Depth-First Search (DFS) or Breadth-First Search (BFS) are the optimal approaches. Both treat rooms as nodes in a graph and keys as directed edges. Starting from room 0, you traverse reachable rooms while marking visited ones. If the number of visited rooms equals n, all rooms are accessible.
Is Keys and Rooms asked at Google/Amazon/Meta?
Keys and Rooms represents a classic graph traversal problem frequently seen in interviews at companies like Amazon, Google, and Meta. Variations of reachability or connected component problems appear regularly in coding interviews.
What data structure is used in Keys and Rooms?
The core structure is a graph represented by an adjacency list where rooms contain keys to other rooms. Traversal uses either a recursion stack for DFS or a queue for BFS, along with a visited set or boolean array to track explored rooms.
What is the time complexity of Keys and Rooms?
The time complexity is O(n + e), where n is the number of rooms and e is the total number of keys across all rooms. Each room is visited at most once and every key is processed once during traversal.