For this problem, since any key we pick up stays with us forever and there's no "cost" or "distance" to minimize, this isn't about bitmasking or finding a specific path—it's a straightforward Graph Traversal problem.

This is a classic Connected Components problem in a directed graph.

The Stack: Represents our "frontier"—the keys we have in our hand but haven't used yet.

The Set: Represents our "knowledge"—the rooms we've already unlocked.

While this problem is simple, there is one detail to watch out for: Is the graph disconnected? Because we start at Room 0, if the graph is split into two "islands" and the second island contains the keys to itself, we will never reach it. The len(visited) == n check is the most elegant way to catch this.

There are two main reasons why the input is usually an array of lists rather than a list of sets, and why we don't bother converting them:

1. Data Redundancy vs. Lookup Speed

In a graph traversal (BFS/DFS), we only visit each room once. When we enter a room, you iterate through every key inside it exactly one time to see where we can go next.

Iteration: Iterating through a List is slightly faster than iterating through a Set because lists have better memory locality (elements are packed together in an array).

Duplicate Keys: Even if a room contains duplicate keys (e.g., rooms[0] = [1, 1, 1]), our visited set handles the logic for us. The if key not in visited check costs $O(1)$. Converting the room's keys into a set just to remove duplicates before we iterate would actually take more time than just letting the visited check skip the duplicates during the crawl.

1. Space Complexity

Converting the input to sets requires $O(K)$ extra space (where $K$ is the total number of keys in all rooms combined). For a large input, this essentially doubles the memory footprint of the problem before we've even started solving it. Since we can achieve the result by just reading the lists as they are, the extra space is generally considered "waste."

https://gemini.google.com/app/69d26671c5e682eb

class Solution:
    def canVisitAllRooms(self, rooms):
        visited = {0}
        stack = [0]
        
        while stack:
            current_room = stack.pop()
            for key in rooms[current_room]:
                if key not in visited:
                    visited.add(key)
                    stack.append(key)
                    
        return len(visited) == len(rooms)