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.

🤓Explanation

Okay, imagine the rooms are like different boxes, and the numbers inside a box are keys to open other boxes. You start with the first box (box number 0). You want to know if you can open all the boxes.

Here's how the code figures that out, in a simple way:

Pseudocode (like a recipe):

1- Keep track of opened boxes: Make a list of all the boxes, and for each box, mark it as "closed" at the beginning.
2- Start with the first box: Open the very first box (box number 0). Mark it as "opened".
3- Make a list of keys to use: Put all the keys you find in the opened box into a special bag of keys.
4- Use the keys:

• While your bag of keys is not empty:
• Take one key out of the bag.
• This key tells you which box it can open.
• If that box is still "closed":
• Open that box and mark it as "opened".
• Take all the new keys you find in this newly opened box and put them into your bag of keys.

5- Check if all boxes are opened: After you can't open any more boxes (your key bag is empty), count how many boxes you've marked as "opened".
6- Tell the answer:

• If the number of opened boxes is the same as the total number of boxes, then you could visit all the rooms (return "Yes!").
• If the number of opened boxes is less than the total number of boxes, then you couldn't visit all the rooms (return "No!").

Time Complexity:

O(N + E), where:

• N is the number of rooms (vertices in the graph).
• E is the total number of keys across all rooms (edges in the graph).
• Explanation:
• Each room will be enqueued and dequeued at most once in the BFS process, taking O(N) time in total for these operations.
• For each room dequeued, we iterate through its list of keys. In the worst case, we might visit all the keys in all the rooms. The total number of keys represents the number of edges in our directed graph. Therefore, iterating through all the adjacency lists takes O(E) time.

Space Complexity:

O(N):

• visited array: This boolean array stores the visited status of each room and has a size proportional to the number of rooms, O(N).
• queue: In the worst-case scenario (e.g., if all rooms are reachable from the starting room), the queue might contain all the rooms at some point, leading to a space complexity of O(N).

⚙️Implementations

🐍Python

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        """
        Determines if it's possible to visit all the rooms starting from room 0.

        The rooms are represented as a list of lists, where each inner list contains the keys
        found in that room. A key with value 'k' allows you to enter room with index 'k'.

        Args:
            rooms (List[List[int]]): A list of lists representing the rooms and the keys they contain.
                                     rooms[i] is a list of keys found in room i.

        Returns:
            bool: True if all rooms can be visited, False otherwise.

        Comment:
        This function uses Breadth-First Search (BFS) to explore the rooms reachable from the starting room (room 0).
        It maintains a 'visited' array to keep track of the rooms that have been accessed.
        The algorithm starts by visiting room 0 and then iteratively explores all the rooms that can be
        reached through the keys found in the currently visited rooms. Finally, it checks if the total
        number of visited rooms equals the total number of rooms. If they are equal, it means all rooms
        are reachable from the starting room, and the function returns True. Otherwise, it returns False.
        This problem can be modeled as a directed graph where each room is a node and a key in room 'i'
        that opens room 'j' represents a directed edge from node 'i' to node 'j'. The problem then becomes
        checking if all nodes in the graph are reachable from the starting node (node 0).
        """
        # get number of vertices (rooms)
        V = len(rooms)

        # keep track of visited rooms
        visited = [False] * V

        # start with room 0
        queue = deque([0])
        visited[0] = True
        visited_count = 0

        while queue:
            current_room = queue.popleft()
            visited_count += 1

            # explore the keys in the current room
            for key in rooms[current_room]:
                # if we haven't visited the room the key unlocks
                if 0 <= key < V and not visited[key]:
                    visited[key] = True
                    queue.append(key)

        # if we have visited all the rooms, return True
        return visited_count == V

🟦Typescript

/**
 * Determines if it's possible to visit all the rooms starting from room 0.
 *
 * The rooms are represented as a list of lists, where each inner list contains the keys
 * found in that room. A key with value 'k' allows you to enter room with index 'k'.
 *
 * @param {number[][]} rooms A list of lists representing the rooms and the keys they contain.
 * rooms[i] is a list of keys found in room i.
 * @returns {boolean} True if all rooms can be visited, false otherwise.
 *
 * @comment
 * This function uses Breadth-First Search (BFS) to explore the rooms reachable from the
 * starting room (room 0).
 * It maintains a 'visited' array to keep track of the rooms that have been accessed.
 * The algorithm starts by visiting room 0 and then iteratively explores all the rooms
 * that can be reached through the keys found in the currently visited rooms.
 * Finally, it checks if the total number of visited rooms equals the total number of rooms.
 * If they are equal, it means all rooms are reachable from the starting room, and the
 * function returns true. Otherwise, it returns false.
 * This problem can be modeled as a directed graph where each room is a node and a key
 * in room 'i' that opens room 'j' represents a directed edge from node 'i' to node 'j'.
 * The problem then becomes checking if all nodes in the graph are reachable from the
 * starting node (node 0).
 */
function canVisitAllRooms(rooms: number[][]): boolean {
    // Get the total number of rooms (vertices in the graph).
    const numRooms = rooms.length;

    // Create a boolean array to keep track of visited rooms.
    // Initially, all rooms are marked as not visited (false).
    const visited: boolean[] = new Array(numRooms).fill(false);

    // Initialize a queue for Breadth-First Search (BFS) and add the starting room (room 0).
    const queue: number[] = [0];

    // Mark the starting room as visited.
    visited[0] = true;

    // Keep track of the number of visited rooms.
    let visitedCount = 0;

    // Perform BFS while the queue is not empty.
    while (queue.length > 0) {
        // Dequeue a room from the front of the queue (the current room being explored).
        const currentRoom = queue.shift()!; // '!' asserts that the queue is not empty.
        visitedCount++;

        // Iterate through the keys found in the current room.
        for (const key of rooms[currentRoom]) {
            // Check if the key corresponds to a valid room index and if that room has not been visited yet.
            if (key >= 0 && key < numRooms && !visited[key]) {
                // Mark the newly reachable room as visited.
                visited[key] = true;
                // Enqueue the newly reachable room to explore its keys later.
                queue.push(key);
            }
        }
    }

    // After BFS, check if the number of visited rooms equals the total number of rooms.
    // If they are equal, it means all rooms were reachable from the starting room.
    return visitedCount === numRooms;
};

🐭Go

/**
 * Determines if it's possible to visit all the rooms starting from room 0.
 *
 * The rooms are represented as a slice of slices of integers, where each inner slice contains the keys
 * found in that room. A key with value 'k' allows you to enter room with index 'k'.
 *
 * @param rooms [][]int A slice of slices representing the rooms and the keys they contain.
 * rooms[i] is a slice of keys found in room i.
 * @return bool True if all rooms can be visited, false otherwise.
 *
 * @comment
 * This function uses Breadth-First Search (BFS) to explore the rooms reachable from the
 * starting room (room 0).
 * It maintains a 'visited' boolean slice to keep track of the rooms that have been accessed.
 * The algorithm starts by visiting room 0 and then iteratively explores all the rooms
 * that can be reached through the keys found in the currently visited rooms.
 * Finally, it checks if the total number of visited rooms equals the total number of rooms.
 * If they are equal, it means all rooms are reachable from the starting room, and the
 * function returns true. Otherwise, it returns false.
 * This problem can be modeled as a directed graph where each room is a node and a key
 * in room 'i' that opens room 'j' represents a directed edge from node 'i' to node 'j'.
 * The problem then becomes checking if all nodes in the graph are reachable from the
 * starting node (node 0).
 */
func canVisitAllRooms(rooms [][]int) bool {
 // Get the total number of rooms (vertices in the graph).
 numRooms := len(rooms)

 // Create a boolean slice to keep track of visited rooms.
 // Initially, all rooms are marked as not visited (false).
 visited := make([]bool, numRooms)

 // Initialize a queue for Breadth-First Search (BFS) and add the starting room (room 0).
 queue := []int{0}

 // Mark the starting room as visited.
 visited[0] = true

 // Keep track of the number of visited rooms.
 visitedCount := 0

 // Perform BFS while the queue is not empty.
 for len(queue) > 0 {
  // Dequeue a room from the front of the queue (the current room being explored).
  currentRoom := queue[0]
  queue = queue[1:]
  visitedCount++

  // Iterate through the keys found in the current room.
  for _, key := range rooms[currentRoom] {
   // Check if the key corresponds to a valid room index and if that room has not been visited yet.
   if key >= 0 && key < numRooms && !visited[key] {
    // Mark the newly reachable room as visited.
    visited[key] = true
    // Enqueue the newly reachable room to explore its keys later.
    queue = append(queue, key)
   }
  }
 }

 // After BFS, check if the number of visited rooms equals the total number of rooms.
 // If they are equal, it means all rooms were reachable from the starting room.
 return visitedCount == numRooms
}

---

If you liked this content I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.

Muchas gracias!

Follow me for more content like this.

X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me | Medium

Down below you can find other ways to tip my work.

BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"