The question is pretty easy, it's all about just clicking the approach.
Difficulty: Medium
Jump To:
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 bitsetkeysCollected
and push into stacks
. - Now perform below operations until the stack
s
becomes empty:- Pop room number from stack,
t
. - If
Room-t
is not visited yet then visit and mark it visited using bitsetvisited
. - Pick those keys from here which open a room which is not visitable yet, which can be checked by
keysCollected
. - For picked keys, mark associated rooms visitable using
keysCollected
and push into stacks
.
- Pop room number from stack,
- If count of visited rooms as per
visited
is equal to the count of total roomsrooms.size()
then returntrue
elsefalse
.
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();
}
};
Runnable C++ code:
Cover Photo by Jaye Haych on Unsplash
Top comments (1)
great explanation.