[LeetCode] 841. Keys and Rooms

1. Question

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.
 

2. Thoughts

Use DFS and maintain visted nodes.

3. Tips learned

4. My solution

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = []
        need_visited = deque([0])
        while need_visited:
            index = need_visited.pop()
            if index not in visited:
                visited.append(index)
                need_visited.extend(rooms[index])

        return len(visited) == len(rooms)

68/68 cases passed (78 ms)
Your runtime beats 19.37 % of python3 submissions
Your memory usage beats 53.98 % of python3 submissions (16.9 MB)

5. AI Solution and Improvements

Your current solution uses a breadth-first search (BFS) strategy to traverse the rooms, which is a suitable approach for this problem. However, there are a few optimizations and improvements that can be made:

1. Use a Set for Visited Rooms: Using a set for visited instead of a list can significantly improve the performance because checking if an element is in a set is O(1), whereas for a list, it's O(n).

2. Change pop() to popleft(): In your code, need_visited is a deque (double-ended queue), but you use pop() which removes and returns an element from the right end of the deque. Since BFS typically processes elements in the order they were added (FIFO - First In First Out), you should use popleft() to remove and return an element from the left end.

3. Avoid Repeatedly Extending need_visited with Already Visited Rooms: Before extending need_visited with keys from the current room, it would be more efficient to filter out the rooms that have already been visited.

Here's the optimized code:

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set()
        need_visited = deque([0])

        while need_visited:
            index = need_visited.popleft()
            if index not in visited:
                visited.add(index)
                need_visited.extend(key for key in rooms[index] if key not in visited)

        return len(visited) == len(rooms)

This optimized version should perform better, especially for cases with a large number of rooms and keys.