Leetcode 841. Keys and Rooms [Solution]

#cpp #algorithms #programming #tutorial

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

Difficulty: Medium
Jump To:

Problem Statement
Explanation
Solution
Implementation

Problem Statement

Question: 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 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

Explanation

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

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:

Mark Room-0 visitable using bitset keysCollected and push into stack s.
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.
If count of visited rooms as per visited is equal to the count of total rooms rooms.size() then return true else false.

Implementation

C++ Code:

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();
    }
};