841. Keys and Rooms

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.

Examples:

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.

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter room number 2 since the only key that unlocks it is in room 2.

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

Python Solution

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = set()
        
        def dfs(room: int) -> None:
            visited.add(room)
            for key in rooms[room]:
                if key not in visited:
                    dfs(key)
        
        dfs(0)
        return len(visited) == n

Implementation Notes:

• Uses DFS to explore rooms and collect keys
• Time complexity: O(N + K) where N is number of rooms and K is total number of keys
• Space complexity: O(N) for visited set and recursion stack

Java Solution

class Solution {
    private Set visited;
    
    public boolean canVisitAllRooms(List> rooms) {
        visited = new HashSet<>();
        dfs(rooms, 0);
        return visited.size() == rooms.size();
    }
    
    private void dfs(List> rooms, int room) {
        visited.add(room);
        for (int key : rooms.get(room)) {
            if (!visited.contains(key)) {
                dfs(rooms, key);
            }
        }
    }
}

C++ Solution

class Solution {
public:
    bool canVisitAllRooms(vector>& rooms) {
        unordered_set visited;
        dfs(rooms, 0, visited);
        return visited.size() == rooms.size();
    }
    
private:
    void dfs(const vector>& rooms, int room, unordered_set& visited) {
        visited.insert(room);
        for (int key : rooms[room]) {
            if (visited.find(key) == visited.end()) {
                dfs(rooms, key, visited);
            }
        }
    }
};

JavaScript Solution

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    const visited = new Set();
    
    const dfs = (room) => {
        visited.add(room);
        for (const key of rooms[room]) {
            if (!visited.has(key)) {
                dfs(key);
            }
        }
    };
    
    dfs(0);
    return visited.size === rooms.length;
};

C# Solution

public class Solution {
    private HashSet visited;
    
    public bool CanVisitAllRooms(IList> rooms) {
        visited = new HashSet();
        DFS(rooms, 0);
        return visited.Count == rooms.Count;
    }
    
    private void DFS(IList> rooms, int room) {
        visited.Add(room);
        foreach (int key in rooms[room]) {
            if (!visited.Contains(key)) {
                DFS(rooms, key);
            }
        }
    }
}

Implementation Notes:

• Uses HashSet for efficient visited room tracking
• DFS implementation with recursion
• Time complexity: O(N + K)
• Space complexity: O(N)