Leetcode 841. Keys and Rooms [Solution]
Tags: cpp, algorithms, programming, tutorial
Published: 2021-03-19 13:30:53

The question is pretty easy, it's all about just clicking the approach.

**Difficulty:** Medium
**Jump To:**
* [Problem Statement](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>

**Question:** [https://leetcode.com/problems/keys-and-rooms/](https://leetcode.com/problems/keys-and-rooms/)



There are  `N`  rooms and you start in room  `0`. Each room has a distinct number in  `0, 1, 2, ..., N-1`, and each room may have some keys to access the next room.

Formally, each room  `i` has a list of keys  `rooms[i]`, and each key  `rooms[i][j]`  is an integer in  `[0, 1, ..., N-1]`  where  `N = rooms.length`. A key  `rooms[i][j] = v` opens the room with number  `v`.

Initially, all the rooms start locked (except for room  `0`).

You can walk back and forth between rooms freely.

Return  `true` if and only if you can enter every room.

**Example 1:**

> **Input:** [[1],[2],[3],[]]
**Output:** true
**Explanation:** 
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

**Example 2:**

> **Input:** [[1,3],[3,0,1],[2],[0]]
**Output:** false
**Explanation:** We can't enter the room with number 2.

**Note:**

1.  `1 <= rooms.length <= 1000`
2.  `0 <= rooms[i].length <= 1000`
3.  The number of keys in all rooms combined is at most `3000`.

---

## Explanation <a name="explanation"></a>

So the problem is simple, We have a room open and we'll find keys of some other rooms then we can visit these rooms and we'll find other keys there. One room can contain no keys as well. We can not visit a room until we have key to it. So we need to find that whether we can visit all rooms or not.

---

## Solution <a name="solution"></a>

Doesn't it like look a graph traversal problem??? Where rooms are like node and keys to other rooms present in a room are like edges to other nodes. And we just need to check whether we can traverse all nodes or not. So we can use **Breadth First Search(BFS)** or **Dreadth First Search(DFS)**. I am using a stack-based DFS approach.

A little enhancement is that I don't want to revisit a node which we have already visited, for that we can use a **bitset** or a boolean array. One more enhancement we can do that, we can prevent collecting keys for the rooms for whom we already have keys. This can be done using another bitset.

So solution is easy:
1. Mark `Room-0` visitable using bitset `keysCollected` and push into stack `s`.
2. Now perform below operations until the stack `s` becomes empty:
	1.  Pop room number from stack, `t`.
	2. If `Room-t` is not visited yet then visit and mark it visited using bitset `visited`.
	3. Pick those keys from here which open a room which is not visitable yet, which can be checked by `keysCollected`.
	4. For picked keys, mark associated rooms visitable using `keysCollected` and push into stack `s`.
3. If count of visited rooms as per `visited` is equal to the count of total rooms `rooms.size()` then return `true` else `false`.

---

## Implementation <a name="implementation"></a>

**C++ Code:**

```cpp
class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms)
    {
        stack<int> s;
        bitset<1000> visited;
        bitset<1000> keysCollected;
        keysCollected[0] = 1;
        s.push(0);

        while (!s.empty()) {
            int t = s.top();
            s.pop();
            if (!visited[t]) {
                visited[t] = 1;
                for (auto i = rooms[t].begin(); i != rooms[t].end(); i++) {
                    if (!keysCollected[*i]) {
                        keysCollected[*i] = 1;
                        s.push(*i);
                    }
                }
            }
        }
        return visited.count() == rooms.size();
    }
};
```

**Runnable C++ code:**

{% replit @shivams136/Leetcode-841-Keys-and-Rooms %}

Cover Photo by <a href="https://unsplash.com/@jaye_haych?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Jaye Haych</a> on <a href="/s/photos/keys?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>