Keys and Rooms

LeetCode 871 | Difficulty: Medium

Medium

Problem Description

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.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**.

Topics: Depth-First Search, Breadth-First Search, Graph Theory

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

---

Solutions

Solution 1: C# (Best: 104 ms)

Metric	Value
Runtime	104 ms
Memory	26.4 MB
Date	2020-01-01

Solution

public class Solution {
    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
            bool[] visited = new bool[rooms.Count];
    Queue<int> q = new Queue<int>();
    
    q.Enqueue(0);
    visited[0] = true;
    while (q.Count != 0)
    {
        var top = q.Dequeue();
        foreach (var roomKey in rooms[top])
        {
            if (visited[roomKey])
            {
                continue;
            }

            visited[roomKey] = true;
            q.Enqueue(roomKey);
        }
    }
    return visited.Count(x=>x==false) == 0;
    }
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.