# 841. Keys and Rooms

## Approach 1: DFS

The solution is oddly very similar to Binary Tree Level Order Traversal

```python
class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        https://leetcode.com/problems/keys-and-rooms/description/
        :type rooms: List[List[int]]
        :rtype: bool
        """
        level = rooms[0]
        rooms[0] = []
        le = len(rooms)
        unlocked = [False]*le
        unlocked[0] = True
        cn = 1
        while level:
            # print(level)
            temp = set()
            for i in level:
                if unlocked[i] == False:
                    unlocked[i] = True
                    cn += 1
                temp |= set(rooms[i])
                rooms[i] = []
            level = temp
        return cn == le
```

Since we have keys to the first room we store those in `level`. We then iterate through the list of available keys and for each room visited we add its keys into `temp`. At the end of iteration, `temp` contains the list of all the new keys we have received and we store them back into `level` for the next iteration. We repeat this until we run out of keys.

Each time we add a key to `temp` we check if we have seen that key before and if not, we append a counter `cn` that maintains the number of rooms unlocked. If in the end this counter is equal to the number of rooms in the list we return `True` else `False`

> **Time Complexity:** *O(N) where N is the number of rooms*
>
> **Space Complexity:** *O(N)*


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://programming.arora-aditya.com/leetcode/depth-first-search/841.-keys-and-rooms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.