841. Keys and Rooms

Approach 1: DFS

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

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)