# Keys and Rooms
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/keys-and-rooms)
Canonical: https://scaleengineer.com/dsa/problems/keys-and-rooms
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [Nvidia](https://scaleengineer.com/companies/nvidia), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Graviton](https://scaleengineer.com/companies/graviton)
---
## 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.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**.

# Approaches
## Naive Iterative Key Collection
This approach simulates the process of collecting keys and visiting rooms in a straightforward, iterative manner. It maintains a set of visited rooms and a set of collected keys. It repeatedly tries to use the collected keys to visit new rooms and gather more keys, continuing this process until no new rooms can be accessed. This method is less efficient than standard graph traversal algorithms because it may re-process keys unnecessarily.
**Time:** O(N * E), where N is the number of rooms and E is the total number of keys. In the worst-case scenario, we might only visit one new room per iteration of the outer `while` loop, leading to N iterations. In each iteration, we iterate through all collected keys, which can be up to E keys in total. This leads to a significantly worse performance compared to linear time graph traversals. · **Space:** O(N + E) to store the `visited` set (size up to N) and the `keys` set (size up to E, the total number of keys).
**Pros:** Relatively easy to understand as it directly simulates the physical process of collecting keys and opening doors.
**Cons:** Inefficient due to repeated processing of keys.; The implementation is more complex and less clean than standard graph traversal algorithms.
### Explanation
We use a `Set` called `visited` to store the indices of rooms we have entered, and another `Set` called `keys` to store all the keys we have collected so far. Initially, we can only enter room 0, so we add 0 to `visited` and collect all keys from `rooms[0]`, adding them to the `keys` set. We then enter a loop that continues as long as we are making progress (i.e., visiting new rooms). Inside the loop, we iterate through a copy of our current `keys`. For each key, if it unlocks a room we haven't visited, we mark that room as visited, collect all the keys from it, and add them to our `keys` set. If an entire pass through our collected keys results in no new rooms being visited, we know we are stuck and can't explore further, so we break the loop. Finally, we check if the number of rooms in our `visited` set is equal to the total number of rooms.
```java
import java.util.HashSet;
import java.util.Set;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        Set<Integer> visited = new HashSet<>();
        Set<Integer> keys = new HashSet<>();
        
        // Start at room 0
        visited.add(0);
        keys.addAll(rooms.get(0));
        
        boolean progressMade = true;
        while (progressMade) {
            progressMade = false;
            Set<Integer> newKeysFound = new HashSet<>();
            
            // Iterate over a copy to avoid ConcurrentModificationException
            List<Integer> keysToTry = new ArrayList<>(keys);

            for (int key : keysToTry) {
                if (!visited.contains(key)) {
                    visited.add(key);
                    newKeysFound.addAll(rooms.get(key));
                    progressMade = true;
                }
            }
            keys.addAll(newKeysFound);
        }
        
        return visited.size() == n;
    }
}
```
### Algorithm
- Initialize a `Set<Integer>` named `visited` and add `0` to it.
- Initialize a `Set<Integer>` named `keys` and add all keys from `rooms.get(0)`.
- Start a `while` loop that continues as long as progress is made in visiting new rooms.
- Inside the loop, set a `progressMade` flag to `false`.
- Create a temporary copy of the `keys` set to iterate over, to avoid modification issues while iterating.
- For each `key` in the copied set:
    - If the room corresponding to `key` has not been visited:
        - Add the `key` to the `visited` set.
        - Add all keys from `rooms.get(key)` to a temporary `newKeysFound` set.
        - Set `progressMade` to `true`.
- After the inner loop, add all keys from `newKeysFound` to the main `keys` set.
- If `progressMade` is `false` after a full iteration, break the `while` loop.
- After the loop terminates, return `true` if `visited.size()` equals the total number of rooms, `false` otherwise.

## Depth-First Search (DFS) Traversal
This approach models the problem as a graph traversal. Each room is a node, and the keys are directed edges. We start a Depth-First Search (DFS) from room 0 to find all reachable rooms. After the traversal, we check if the number of visited rooms equals the total number of rooms. This is an efficient and standard way to solve connectivity problems in graphs.
**Time:** O(N + E), where N is the number of rooms and E is the total number of keys. In the worst case, we visit each room (node) and each key (edge) exactly once. · **Space:** O(N) for the `visited` array. In the recursive approach, the space complexity also includes the recursion stack, which can be O(N) in the worst case (e.g., a graph where rooms form a single long chain). The iterative approach uses a stack that can also grow to O(N).
**Pros:** Efficient and optimal solution.; Standard, well-understood algorithm for graph traversal.; The recursive implementation is very concise and elegant.
**Cons:** The recursive version could theoretically cause a stack overflow if the graph is extremely deep, though this is not an issue with the given constraints (N <= 1000).
### Explanation
The problem can be seen as finding if all nodes in a directed graph are reachable from a starting node (room 0). DFS is a natural fit for this. We use a boolean array `visited` to keep track of the rooms we have entered. We can implement DFS either recursively or iteratively using a stack. The recursive approach is often more concise. We start the `dfs` function from room 0. In the function, we first mark the current room as visited. Then, for each key in the current room, we check if the room it unlocks has been visited. If not, we make a recursive call to `dfs` for that new room. This process continues until we have explored all reachable rooms from room 0. After the initial `dfs(0)` call returns, we iterate through our `visited` array. If any room is marked as `false`, it means it was unreachable, so we return `false`. If all rooms are `true`, we return `true`.

**Recursive DFS:**
```java
import java.util.List;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];
        dfs(0, rooms, visited);
        
        for (boolean roomVisited : visited) {
            if (!roomVisited) {
                return false;
            }
        }
        return true;
    }
    
    private void dfs(int room, List<List<Integer>> rooms, boolean[] visited) {
        if (visited[room]) {
            return;
        }
        visited[room] = true;
        for (int key : rooms.get(room)) {
            dfs(key, rooms, visited);
        }
    }
}
```

**Iterative DFS:**
```java
import java.util.List;
import java.util.Stack;

class SolutionIterative {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];
        Stack<Integer> stack = new Stack<>();
        
        stack.push(0);
        visited[0] = true;
        int count = 1;
        
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : rooms.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                    count++;
                }
            }
        }
        
        return count == rooms.size();
    }
}
```
### Algorithm
- Initialize a boolean array `visited` of size `n` (number of rooms) to all `false`.
- Define a recursive function `dfs(room, rooms, visited)`.
- Call `dfs(0, rooms, visited)` to start the traversal from room 0.
- Inside `dfs(room, ...)`:
    - Mark the current `room` as visited: `visited[room] = true`.
    - Get the list of keys for the current `room`.
    - For each `key` in the list:
        - If the room `key` has not been visited (`!visited[key]`), recursively call `dfs(key, rooms, visited)`.
- After the initial `dfs` call completes, iterate through the `visited` array.
- If any element `visited[i]` is `false`, return `false`.
- If the loop completes without finding any unvisited rooms, return `true`.

## Breadth-First Search (BFS) Traversal
This approach also treats the problem as a graph traversal, but uses Breadth-First Search (BFS) instead of DFS. Starting from room 0, it explores rooms level by level. It uses a queue to manage the rooms to visit. This method is equally efficient as DFS and is another standard technique for solving graph connectivity problems.
**Time:** O(N + E), where N is the number of rooms and E is the total number of keys. Each room is enqueued and dequeued once, and each key is checked once. · **Space:** O(N) for the `visited` array. The space for the queue can also be up to O(N) in the worst case (e.g., a star graph where room 0 has keys to all other rooms).
**Pros:** Efficient and optimal solution.; Iterative by nature, so it avoids recursion depth limits.; Finds the shortest path in terms of edges (number of rooms visited) to any node, although not required here.
**Cons:** Generally requires slightly more code than a recursive DFS.; No significant performance difference from DFS for this problem.
### Explanation
BFS explores the graph layer by layer from the source node (room 0). This is achieved using a queue data structure. We initialize a `Queue` and add room 0 to it. We also use a `visited` array (or set) to avoid processing rooms more than once and to prevent cycles. We mark room 0 as visited and add it to the queue. We also keep a `count` of visited rooms. The main loop continues as long as the queue is not empty. In each iteration, we dequeue a room. For this room, we iterate through all the keys it contains. For each key, if the corresponding room has not been visited, we mark it as visited, increment our `count`, and enqueue it. After the loop finishes, all reachable rooms will have been visited. We simply compare our `count` of visited rooms with the total number of rooms (`n`). If they match, it means all rooms were reachable.
```java
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        
        // Start with room 0
        visited[0] = true;
        queue.add(0);
        int visitedCount = 1;
        
        while (!queue.isEmpty()) {
            int currentRoom = queue.poll();
            
            for (int key : rooms.get(currentRoom)) {
                if (!visited[key]) {
                    visited[key] = true;
                    queue.add(key);
                    visitedCount++;
                }
            }
        }
        
        return visitedCount == n;
    }
}
```
### Algorithm
- Initialize a boolean array `visited` of size `n` to all `false`.
- Initialize a `Queue<Integer>` and add `0` to it.
- Mark room 0 as visited: `visited[0] = true`.
- Initialize a counter `visitedCount` to 1.
- While the queue is not empty:
    - Dequeue a room, let's call it `currentRoom`.
    - For each `key` in `rooms.get(currentRoom)`:
        - If room `key` has not been visited (`!visited[key]`):
            - Mark it as visited: `visited[key] = true`.
            - Enqueue the `key`.
            - Increment `visitedCount`.
- After the loop, return `true` if `visitedCount` equals `n`, `false` otherwise.

# Solutions
### Java

```java
class Solution { private List < List < Integer >> rooms ; private Set < Integer > vis ; public boolean canVisitAllRooms ( List < List < Integer >> rooms ) { vis = new HashSet <>(); this . rooms = rooms ; dfs ( 0 ); return vis . size () == rooms . size (); } private void dfs ( int u ) { if ( vis . contains ( u )) { return ; } vis . add ( u ); for ( int v : rooms . get ( u )) { dfs ( v ); } } }
```

### CPP

```cpp
class Solution { public: vector < vector < int >> rooms ; unordered_set < int > vis ; bool canVisitAllRooms ( vector < vector < int >>& rooms ) { vis . clear (); this -> rooms = rooms ; dfs ( 0 ); return vis . size () == rooms . size (); } void dfs ( int u ) { if ( vis . count ( u )) return ; vis . insert ( u ); for ( int v : rooms [ u ]) dfs ( v ); } };
```

### Python

```python
class Solution : def canVisitAllRooms ( self , rooms : List [ List [ int ]]) -> bool : def dfs ( u ): if u in vis : return vis . add ( u ) for v in rooms [ u ]: dfs ( v ) vis = set () dfs ( 0 ) return len ( vis ) == len ( rooms )
```