> For the complete documentation index, see [llms.txt](https://programming.arora-aditya.com/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://programming.arora-aditya.com/leetcode/depth-first-search/841.-keys-and-rooms.md).

# 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)*