# 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

| Item | Meaning |
|---|---|
| Input | `rooms`, where `rooms[i]` is the list of keys inside room `i` |
| Output | `True` if every room can be visited, otherwise `False` |
| Start | Room `0` is initially unlocked |
| Key rule | A key labeled `x` unlocks room `x` |
| Graph view | Rooms are nodes, keys are directed edges |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
True
```

Example 2:

```python
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:

```python
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:

```python
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:

| State | Meaning |
|---|---|
| `visited[i]` | Whether room `i` has already been entered |
| `stack` | Rooms we have keys for and still need to process |

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:

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

Start:

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

Pop room `0`.

It has key `1`, so visit room `1`:

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

Pop room `1`.

It has key `2`, so visit room `2`:

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

Pop room `2`.

It has key `3`, so visit room `3`:

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

Pop room `3`.

It has no keys.

The stack becomes empty.

All rooms are visited, so return:

```python
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:

```python
n = number of rooms
k = total number of keys
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + k)` | Each room is visited once, and each key is inspected once |
| Space | `O(n)` | The visited array and stack store room indices |

## Implementation

```python
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:

```python
visited = [False] * n
```

Room `0` is initially open:

```python
stack = [0]
visited[0] = True
```

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

For each room:

```python
room = stack.pop()
```

we collect its keys:

```python
for key in rooms[room]:
```

If a key opens a room we have not visited:

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

we mark it and process it later.

Finally:

```python
return all(visited)
```

checks whether every room was reached.

## Testing

```python
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:

| Test | Why |
|---|---|
| Linear chain | Confirms keys can unlock rooms step by step |
| Missing key | Confirms unreachable room returns `False` |
| One room | Confirms room `0` alone is already visited |
| Disconnected room | Confirms unused component stays locked |
| Branching keys | Confirms multiple keys from one room work |