Keys and Rooms

Q: Does it matter whether I use DFS or BFS?

No. Both visit exactly the rooms reachable from room 0, in the same O(n + K) time. The order of visits differs, but the question only asks whether all rooms are reached.

mediumGraphs

There are n rooms numbered 0 to n - 1. Room 0 is open; every other room starts locked. Inside room i is a set of keys, given as rooms[i], where each key is the number of the room it opens. Keys can be reused, and you may revisit rooms freely.

Return true if you can end up entering every room, and false otherwise.

Examples

Example 1

Input: rooms = [[2], [], [1, 3], []]

Output: true

Explanation: Room 0 gives the key to 2. Room 2 gives keys to 1 and 3. Every room is now open.

Example 2

Input: rooms = [[1], [0], [3], [2]]

Output: false

Explanation: Rooms 0 and 1 only hold keys to each other. The keys for rooms 2 and 3 are locked inside rooms 2 and 3.

Hints

Approach

Graph reachability with a depth-first search from room 0. Visit each room once, the moment you first get its key.

Mark room 0 visited and push it on a stack.
Pop a room and look at its keys. For each key to an unvisited room, mark that room visited and push it.
Count rooms as you mark them. At the end, compare the count with n.

Each room is pushed at most once and each key is read once, so the work is proportional to rooms plus keys.

ComplexityTime O(n + K)Space O(n)

Python

class Solution:
    def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
        visited = [False] * len(rooms)
        visited[0] = True
        count = 1
        stack = [0]
        while stack:
            room = stack.pop()
            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    count += 1
                    stack.append(key)
        return count == len(rooms)

Follow-up questions

Return the list of rooms that can never be opened.
Some keys only work once. Does the problem still reduce to plain reachability?

Frequently asked questions

No. Both visit exactly the rooms reachable from room 0, in the same O(n + K) time. The order of visits differs, but the question only asks whether all rooms are reached.

It is the shape of any "what can I reach starting from here" audit: starting from a bastion host, which machines are reachable through the SSH keys stored on each hop? Starting from one IAM role, which other roles can it assume in a chain? A reachability search from one start node answers both.