LeetCode 841: Keys and Rooms

Problem Restatement

We are given n rooms numbered from 0 to n - 1.

All rooms are locked except room 0.

Each room contains keys. A key is represented by an integer, and key x unlocks room x.

When we enter a room, we can take all keys inside it.

Return True if we can visit every room. Otherwise, return False.

Input and Output

Function shape:

class Solution:
    def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
        ...

Examples

Example 1:

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

Start in room 0.

Room 0 gives key 1.

Room 1 gives key 2.

Room 2 gives key 3.

Now all rooms can be visited.

So the answer is:

True

Example 2:

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

Start in room 0.

From room 0, we can visit rooms 1 and 3.

Room 1 gives keys 3, 0, and 1.

Room 3 gives key 0.

There is no way to get key 2.

So room 2 cannot be visited.

The answer is:

False

First Thought: Treat Rooms as a Graph

This is a reachability problem.

Each room is a node.

Each key inside a room is a directed edge to another room.

For example:

rooms[i] = [a, b, c]

means from room i, we can go to rooms a, b, and c.

The question becomes:

Can we reach every node starting from node 0?

That is a standard DFS or BFS problem.

Key Insight

We do not need to simulate locks separately.

A room is visitable if we have reached it from room 0.

Once we visit a room, we can use every key inside it.

So we only need:

Every time we pop a room, we collect its keys and add newly discovered rooms to the stack.

Algorithm

1. Create a visited array of size n.
2. Start with room 0 in the stack.
3. Mark room 0 as visited.
4. While the stack is not empty:
   1. Pop one room.
   2. Look at every key in that room.
   3. If the key opens an unvisited room, mark it visited and push it.
5. Return whether all rooms were visited.

Walkthrough

Use:

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

Start:

visited = [True, False, False, False]
stack = [0]

Pop room 0.

It has key 1, so visit room 1:

visited = [True, True, False, False]
stack = [1]

Pop room 1.

It has key 2, so visit room 2:

visited = [True, True, True, False]
stack = [2]

Pop room 2.

It has key 3, so visit room 3:

visited = [True, True, True, True]
stack = [3]

Pop room 3.

It has no keys.

The stack becomes empty.

All rooms are visited, so return:

True

Correctness

The algorithm starts from room 0, the only room that is initially unlocked.

Whenever the algorithm visits a room, it examines every key in that room. If a key unlocks an unvisited room, the algorithm marks that room visited and adds it for later processing.

Therefore, every room reachable from room 0 through collected keys will eventually be visited.

The algorithm never marks a room visited unless it has found a key path to that room from room 0. So every visited room is actually reachable.

At the end, visited contains exactly the rooms reachable from room 0.

If every value in visited is True, every room can be visited. If at least one value is False, that room is unreachable.

Therefore, the algorithm returns the correct answer.

Complexity

Let:

n = number of rooms
k = total number of keys

Implementation

class Solution:
    def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n

        stack = [0]
        visited[0] = True

        while stack:
            room = stack.pop()

            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    stack.append(key)

        return all(visited)

Code Explanation

We create a visited array:

visited = [False] * n

Room 0 is initially open:

stack = [0]
visited[0] = True

The stack stores rooms we can enter but have not fully processed yet.

For each room:

room = stack.pop()

we collect its keys:

for key in rooms[room]:

If a key opens a room we have not visited:

if not visited[key]:
    visited[key] = True
    stack.append(key)

we mark it and process it later.

Finally:

return all(visited)

checks whether every room was reached.

Testing

def run_tests():
    s = Solution()

    assert s.canVisitAllRooms([[1], [2], [3], []]) is True
    assert s.canVisitAllRooms([[1, 3], [3, 0, 1], [2], [0]]) is False
    assert s.canVisitAllRooms([[]]) is True
    assert s.canVisitAllRooms([[1], [], [0]]) is False
    assert s.canVisitAllRooms([[1, 2], [2], [3], []]) is True

    print("all tests passed")

run_tests()

Test meaning: